Loading ...
Sorry, an error occurred while loading the content.

Re: [hackers-il] Finding the Graham's Function

Expand Messages
  • Shlomi Fish
    ... OK, so I ll revamp it. I think I ll dedicate an entire slide to it. ... Actually it s if n + largest_factor is factored to an even power of largest_factor.
    Message 1 of 5 , Jul 31, 2003
    • 0 Attachment
      On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

      > Shlomi Fish wrote on 2003-07-30:
      >
      > > Here:
      > >
      > > http://vipe.technion.ac.il/~shlomif/lecture/Perl/Graham-Function/
      > >
      > > You can find a lecture and Perl code I wrote for finding the Graham
      > > Function. It was done as part of one of Mark Jason Dominus' Perl Quizes of
      > > the Week.
      > >
      > > To calculate the Graham Function one needs to find an increasing sequence
      > > of integers starting from the integer in question, so that their product
      > > is a perfect square and the largest number is as small as possible. Then,
      > > the graham function is the largest number.
      > >
      > > My solution to the problem uses some Linear Algebra concepts to solve the
      > > problem.
      > >
      > Cute! I've just read some { Graham (this one!), Knuth (the one ;),
      > Patashnik }'s "Concrete Mathematics" so I can't resist studying such a
      > problem ;-). Some notes:
      >
      > - The `n + largest_factor` optimization is relatively poorly
      > explained, especially in the lecture notes --

      OK, so I'll revamp it. I think I'll dedicate an entire slide to it.

      > at least it took me
      > lots of time and code studying to understand it, while the rest was
      > easy. The explanation doesn't mentions that you might need `n +
      > 2*largest_factor` if `n + largest_factor` divides by
      > `largest_factor` an even number of times.

      Actually it's if n + largest_factor is factored to an even power of
      largest_factor.

      > It uses a "SqFact"
      > notation that doesn't appear anywhere else, confusing because
      > "get_squaring_factors()" is used near it. And most importantly,
      > s/fit a square of /fit any square * /; I couldn't make any sense of
      > this sentence for a long time.
      >

      OK, I'll fix it.

      > - A simple experiment (add ``print "optimized";`` and grep -c for it)
      > gives a fascinating result: this optimization works with apparently
      > constant probability of about 43% over any range of consecutive
      > numbers! Perhaps not constant -- but it decreases very slowly. I
      > probed short ranges up to ~270000:
      >
      > 1000-2000: 436/1001 = 0.436
      > 2000-3000: 437/1001 = 0.437
      > 10000-10100: 44/101 = 0.436
      > 20000-20100: 42/101 = 0.416
      > 70000-70100: 39/101 = 0.386
      > 200000-200020: 7/21 = 0.333
      > 267800-267820: 6/21 = 0.285
      >
      > The last results suggest slow decrease but their precision is low
      > (for big numbers I took ranges of only 20 numbers since it takes
      > ages to run). Any explanation? Where does 0.43 come from? I bet
      > it involves pi or e :-).
      >

      You can easily implement a function that runs only this optimization and
      fails otherwise. That way it will take much less time, and you can run it
      on longer ranges.

      >
      > P.S. without arguments it executed Graham(0) which nastily exhausted
      > all memory :-(.
      >

      He heh. Guess it's a bug.

      Regards,

      Shlomi Fish

      >



      ----------------------------------------------------------------------
      Shlomi Fish shlomif@...
      Home Page: http://t2.technion.ac.il/~shlomif/

      An apple a day will keep a doctor away. Two apples a day will keep two
      doctors away.

      Falk Fish
    • Shlomi Fish
      OK, the revamped slides are available here: http://vipe.technion.ac.il/~shlomif/lecture/Perl/Graham-Function/ Regards, Shlomi Fish ... Shlomi Fish
      Message 2 of 5 , Jul 31, 2003
      • 0 Attachment
        OK, the revamped slides are available here:

        http://vipe.technion.ac.il/~shlomif/lecture/Perl/Graham-Function/

        Regards,

        Shlomi Fish



        ----------------------------------------------------------------------
        Shlomi Fish shlomif@...
        Home Page: http://t2.technion.ac.il/~shlomif/

        An apple a day will keep a doctor away. Two apples a day will keep two
        doctors away.

        Falk Fish
      • Shlomi Fish
        ... Here are my experminet results (don t calculate the entire function - just checks if the optimization works or not): 1000-2000 : 436 2000-3000 : 437
        Message 3 of 5 , Aug 8, 2003
        • 0 Attachment
          On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

          > Shlomi Fish wrote on 2003-07-30:
          >
          > > Here:
          > >
          > > http://vipe.technion.ac.il/~shlomif/lecture/Perl/Graham-Function/
          > >
          > > You can find a lecture and Perl code I wrote for finding the Graham
          > > Function. It was done as part of one of Mark Jason Dominus' Perl Quizes of
          > > the Week.
          > >
          > > To calculate the Graham Function one needs to find an increasing sequence
          > > of integers starting from the integer in question, so that their product
          > > is a perfect square and the largest number is as small as possible. Then,
          > > the graham function is the largest number.
          > >
          > > My solution to the problem uses some Linear Algebra concepts to solve the
          > > problem.
          > >
          > Cute! I've just read some { Graham (this one!), Knuth (the one ;),
          > Patashnik }'s "Concrete Mathematics" so I can't resist studying such a
          > problem ;-). Some notes:
          >
          > - The `n + largest_factor` optimization is relatively poorly
          > explained, especially in the lecture notes -- at least it took me
          > lots of time and code studying to understand it, while the rest was
          > easy. The explanation doesn't mentions that you might need `n +
          > 2*largest_factor` if `n + largest_factor` divides by
          > `largest_factor` an even number of times. It uses a "SqFact"
          > notation that doesn't appear anywhere else, confusing because
          > "get_squaring_factors()" is used near it. And most importantly,
          > s/fit a square of /fit any square * /; I couldn't make any sense of
          > this sentence for a long time.
          >
          > - A simple experiment (add ``print "optimized";`` and grep -c for it)
          > gives a fascinating result: this optimization works with apparently
          > constant probability of about 43% over any range of consecutive
          > numbers! Perhaps not constant -- but it decreases very slowly. I
          > probed short ranges up to ~270000:
          >
          > 1000-2000: 436/1001 = 0.436
          > 2000-3000: 437/1001 = 0.437
          > 10000-10100: 44/101 = 0.436
          > 20000-20100: 42/101 = 0.416
          > 70000-70100: 39/101 = 0.386
          > 200000-200020: 7/21 = 0.333
          > 267800-267820: 6/21 = 0.285
          >
          > The last results suggest slow decrease but their precision is low
          > (for big numbers I took ranges of only 20 numbers since it takes
          > ages to run). Any explanation? Where does 0.43 come from? I bet
          > it involves pi or e :-).
          >

          Here are my experminet results (don't calculate the entire function -
          just checks if the optimization works or not):

          1000-2000 : 436
          2000-3000 : 437
          10000-11000 : 437
          20000-21000 : 428
          70000-71000 : 439
          200000-201000 : 398
          267800-268800 : 400

          What that means - I don't know. It seems that after 200,000 the ratio has
          decreased to about 0.4 instead of 0.43.

          Regards,

          Shlomi Fish


          ----------------------------------------------------------------------
          Shlomi Fish shlomif@...
          Home Page: http://t2.technion.ac.il/~shlomif/

          An apple a day will keep a doctor away. Two apples a day will keep two
          doctors away.

          Falk Fish
        Your message has been successfully submitted and would be delivered to recipients shortly.