I 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<<bshift;
do{
uint32_t t;
t=(((uint32_t)g<<1)+b)<<bshift;
if(t<=_val){
g+=b;
_val-=t;
}
b>>=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;i<32768;i++){
int gs = GaussSum(i);
eint+=InverseGaussSumInt(gs)!=i;
efloat+=InverseGaussSum(gs)!=i;
}
printf("Errors, int: %d float: %d\n",eint,efloat);
return 0;
}
$ gcc -o test1 -Wall -Wextra ./test1.c -lm && ./test1
Errors, int: 0 float: 11802
The first error in the article's function is at 5793 for me, but I wouldn't be confident that platform/compiler/optimization differences changed the behavior somewhat.
If 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.
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.
A 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.)
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.
Whenever you visit a node you need one edge to walk in and one to walk out, except for the first and last node.
So all K_n with even n , you can walk all the edges.
For odd n, you lose one edge per node, except for 2 of them
I could be mixing things up here, it's been too long ago. I think this was about a directed graph, so the number of edges is actually N^2 and your walk roughly of that length.
To walk a fully connected graph with a prime number of vertices you can walk first to x+1, then x+2 then x+3 etc. edges by looping around. This a fun special case to prove (basically if you loop by x+i where i coprime to n, it loops after visiting all the vertices, and if n is prime every i is coprime to it)
Sounds like a traveling salesman problem... Perhaps if you look at a dual graph where the edges are collapsed into nodes and the nodes are stretched out to become edges? Then the problem statement of "visiting each city only once" might become equivalent.
16 comments
[ 3.0 ms ] story [ 41.7 ms ] threadHe 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.)
A fully connected graph with an even number of vertices will have odd degrees for all of them, and so can't have an Eulerian path.