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

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

Expand Messages
  • 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 1 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 2 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.