Inverting Gauss’ Formula
blog.demofox.org
Inverting Gauss’ Formula
1–10 of 17 posts
Re: Inverting Gauss’ Formula
#2I found the use of floating point dubious, it only took me a minute to eliminate it, most of which was spent finding and pasting an integer square root :).
#include "stdio.h"
#include "math.h"
#include "stdint.h"
/*integer sqrt from libopus*/
unsigned isqrt32(uint32_t _val){
unsigned b;
unsigned g;
int bshift;
g=0;
bshift=((32-__builtin_clz(_val))-1)>>1;
b=1U>=1;
bshift--;
}
while(bshift>=0);
return g;
}
int InverseGaussSumInt(uint32_t sum)
{
return (isqrt32(8*sum+1)-1)>>1;
}
int InverseGaussSum(int sum)
{
return (int)floor(sqrt(2.0f * (float)sum + 0.25) - 0.5f);
}
int GaussSum(int N)
{
return N * (N + 1) / 2;
}
int main(void){
int i;
int eint=0;
int efloat=0;
/*GaussSum(65535/2)==(2^32-1)/8*/
for(i=0;iRe: Inverting Gauss’ Formula
#3I found the use of floating point dubious, it only took me a minute to eliminate it, most of which was spent finding and pasting an integer square root :). #include "stdio.h" #include "math.h" #include "stdint.h" /*integer sqrt from libopus*/ unsigned isqrt32(uint32_t _val){ unsigned b; unsigned g; int bshift; g=0; bshift=((32-__builtin_clz(_val))-1)>>1; b=1U >=1; bshift--; } while(bshift>=0); return g; } int Inverse…
Nice improvement!
Re: Inverting Gauss’ Formula
#4If you have young kids (6 or 7) who understand multiplication and like math, Gauss's formula is such a magical thing to show them, because it seems like it'd be impossible to shortcut adding up all those numbers that way, on the surface, and it's such an easy thing to prove visually.
Re: Inverting Gauss’ Formula
#5A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula.
He told me they are using such an algorithm in some of their products and he picks the brain of potential hires to see if they find a more elegant way of doing so. Left a great impression, he really cared about thought processes and communicating! (I didn't end up taking the job for reasons unrelated to the company or the offer.)
Re: Inverting Gauss’ Formula
#6A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
Isn't the length of the walk the number of edges?
Re: Inverting Gauss’ Formula
#7If you have young kids (6 or 7) who understand multiplication and like math, Gauss's formula is such a magical thing to show them, because it seems like it'd be impossible to shortcut adding up all those numbers that way, on the surface, and it's such an easy thing to prove visually.
Heck, it was magical to me when I first learned it in my 20s.
Re: Inverting Gauss’ Formula
#8If you have young kids (6 or 7) who understand multiplication and like math, Gauss's formula is such a magical thing to show them, because it seems like it'd be impossible to shortcut adding up all those numbers that way, on the surface, and it's such an easy thing to prove visually.
The other thing I like to show kids is how to count to a thousand (1023 to be precise) on their hands. Algorithm is simple, you just start from the outside of your hand (I use thumb as first position) and then to get a new inner most finger you must collapse all outward fingers. This is of course binary (00000, 00001, 00010, 00011, 00100, ...). Kinds love this and it feels like a super-power to them. Just be careful with teenagers because 4 has a problematic representation. But great way to discuss how counting systems and digit representation work. There's a nice puzzle too, that you can ask them how many "this" is with all fingers open. They usually need a hint, where you ask them how many an 11th finger would be. Funny thing is that kids usually pick up the counting system far faster than adults but adults tend to get the puzzle solved much faster.
Re: Inverting Gauss’ Formula
#9A while back I interviewed with a networking company in the bay area and one of the things the interviewer asked me do was to devise an algorithm to walk the fully connected graph without visiting any edge twice if possible. Was a nice problem to discuss, he moved me along nicely in my thought process and we eventually reached a recursive solution. So the length of this walk is basically this formula. He told me they…
Isn't the length of the walk the number of edges?
I think the parent was agreeing with you, but saying that the number of edges on the fully connected (usually called complete) graph on n vertices is 1 + 2 + 3 + … + n = n(n + 1)/2.
Re: Inverting Gauss’ Formula
#10If you have young kids (6 or 7) who understand multiplication and like math, Gauss's formula is such a magical thing to show them, because it seems like it'd be impossible to shortcut adding up all those numbers that way, on the surface, and it's such an easy thing to prove visually.
It generalizes to any arithmetic sequence. Intuitively, you're simply taking the average of all values (which is the midpoint for a sequence of evenly-spaced numbers) and multiplying by the number of values.