Inverting Gauss’ Formula(blog.demofox.org)

blog.demofox.org

https://blog.demofox.org/2023/08/21/inverting-gauss-formula/

3 comments

nullc3 anni fa

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.

Atrix2563 anni fa

Nice improvement!

phalf3 anni fa

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.)

dcanelhas3 anni fa

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.

a_e_k3 anni fa

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.

phalf3 anni fa

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.

hgsgm3 anni fa

/r/2IsNotEven

bibanez3 anni fa

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)

sorokod3 anni fa

Isn't the length of the walk the number of edges?

vince34553 anni fa

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

JadeNB3 anni fa

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.

empath-nirvana3 anni fa

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.

godelski3 anni fa

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.

nonameiguess3 anni fa

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.

nerdponx3 anni fa

Heck, it was magical to me when I first learned it in my 20s.

3abiton3 anni fa

HN never fails to surprise me