[HN Gopher] Inverting Gauss' Formula
___________________________________________________________________
Inverting Gauss' Formula
Author : ingve
Score : 38 points
Date : 2023-08-22 05:50 UTC (17 hours ago)
(HTM) web link (blog.demofox.org)
(TXT) w3m dump (blog.demofox.org)
| phalf wrote:
| 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.)
| bibanez wrote:
| 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)
| sorokod wrote:
| Isn't the length of the walk the number of edges?
| vince3455 wrote:
| 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
| JadeNB wrote:
| 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.
| a_e_k wrote:
| I assume that's only possible in the general case for an odd
| number of vertices?
|
| 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.
| empath-nirvana wrote:
| 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.
| nerdponx wrote:
| Heck, it was magical to me when I first learned it in my 20s.
| 3abiton wrote:
| HN never fails to surprise me
| godelski wrote:
| 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.
| nonameiguess wrote:
| 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.
| nullc wrote:
| 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.
| Atrix256 wrote:
| Nice improvement!
___________________________________________________________________
(page generated 2023-08-22 23:01 UTC)