- On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

> Shlomi Fish wrote on 2003-07-30:

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

>

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

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

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

largest_factor.

> It uses a "SqFact"

OK, I'll fix it.

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

You can easily implement a function that runs only this optimization and

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

>

fails otherwise. That way it will take much less time, and you can run it

on longer ranges.

>

He heh. Guess it's a bug.

> P.S. without arguments it executed Graham(0) which nastily exhausted

> all memory :-(.

>

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 - 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 - On Wed, 30 Jul 2003, Beni Cherniavsky wrote:

> Shlomi Fish wrote on 2003-07-30:

Here are my experminet results (don't calculate the entire function -

>

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

>

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