Roots of Big Integers

[danbaron]

I got the idea for finding the roots of big integers, from Johannes.

I think he did it in his big integer module.

Racket has big integers automatically.

Below is shown the root finding code, and some results using the Racket REPL (read-eval-print loop).

I timed some of the REPL interactions - the ones which did not seem to be instantaneous.

All of the times are in seconds.

:idea: :!: :?:


' code ----------------------------------------------------------------------------------------------------------------

#lang racket

(define (power x n)
(define product 1)
(define (loop n)
(cond
((= n 0) product)
(else (set! product (* product x))
(loop (- n 1)))))
(loop n))

(define (root x n)
(define below 0)
(define above x)
(define (loop)
(define r (round (/ (+ below above) 2)))
(define p (power r n))
(cond
((<= (- above below) 1) below)
((<= p x)
(set! below r)
(loop))
(else
(set! above r)
(loop))))
(cond
((= n 0) #f)
((= x 1) 1)
((= n 1) x)
(else
(loop))))

(define (time-function f x n)
(let ((t1 (current-milliseconds)))
(let ((result (f x n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values result tt))))))

(define (num-digits n)
(define ns (number->string n))
(define sl (string->list ns))
(length sl))

' REPL interactions ---------------------------------------------------------------------------------------------------

' If r is the nth root of x, then, r^n = x, yes or no?

'------------------------------------------------------

' All of the roots of 1 should be 1, right?

> (root 1 13)
1
>

' What is a 0th root?

> (root 3 0)
#f
>

' The 1st root of x, is x.

> (root 123 1)
123
>

' Everything here is done with integers.
' root function rule: --> If the nth root of x is not an exact integer, the root function will return the largest integer, r, such that r^n < x.

> (root 100 2)
10
> (root 100 3)
4
> (define a (power 97 97))
> (root a 97)
97
> (root a 96)
101
> (root a 98)
92
>

' Below, a = 2^100.
' So, the 100th root of a, is 2.
' The 101st root of a must be 1, 2 would be too big, i.e., 2^101 > a. (See the rule, above.)
' The 99th root of a is also 2, 3 would be too big, i.e., 3^99 > a.
' .
' .
' The 64th root of a is also 2, 3 would be too big, i.e., 3^64 > a.
' The 63rd root of a is 3. 3^63 < a.

> (define a (power 2 100))
> a
1267650600228229401496703205376
> (root a 100)
2
> (root a 101)
1
> (root a 99)
2
> (root a 64)
2
> (root a 63)
3
> (power 3 63)
1144561273430837494885949696427
>

> (define a (power 387 100))
> (num-digits a)
259
> (time-function root a 100)
387
17.175
> (define a (power 387 120))
> (num-digits a)
311
> (time-function root a 120)
387
47.19
> (define a (power 387 140))
> (num-digits a)
363
> (time-function root a 140)
387
95.113
> (define a (power 387 160))
> (num-digits a)
415
> (time-function root a 160)
387
177.044
>

> (define a 6857468364758627564768)
> (define b (power a 11))
> (time-function root b 11)
6857468364758627564768
0.187
> (define b (power a 22))
> (time-function root b 22)
6857468364758627564768
5.85
> (define b (power a 28))
> (time-function root b 28)
6857468364758627564768
20.28
> (define b (power a 32))
> (time-function root b 32)
6857468364758627564768
33.384
> (define b (power a 36))
> (time-function root b 36)
6857468364758627564768
55.162
> (define b (power a 40))
> (time-function root b 40)
6857468364758627564768
86.689
> (define b (power a 51))
> (num-digits b)
1114
> (time-function root b 51)
6857468364758627564768
261.783
> (time-function root b 50)
18745070969977275018761
260.965
> (time-function root b 52)
2607579665186594311711
280.085
>

> (define a 64758365791029103867501928597010809643313974301243)
> (num-digits a)
50
> (define b (power a 10))
> (time-function root b 10)
64758365791029103867501928597010809643313974301243
1.662
> (define b (power a 20))
> (time-function root b 20)
64758365791029103867501928597010809643313974301243
36.572
> (define b (power a 30))
> (time-function root b 30)
64758365791029103867501928597010809643313974301243
208.862
> (define b (power a 40))
> (time-function root b 40)
64758365791029103867501928597010809643313974301243
756.792
> (define b (power a 53))
> (num-digits b)
2640
> (time-function root b 53)
64758365791029103867501928597010809643313974301243
2746.575
>

> (define a 97)
> (define b (power a 100))
> (time-function root b 100)
97
8.731
> (define b (power a 200))
> (time-function root b 200)
97
268.261
> (define b (power a 300))
> (time-function root b 300)
97
1866.335
> (num-digits b)
597
>

> (define a 4968471029485769708957382910584867290793102859201859837486930281964323540987953617859603728190508050)
> (num-digits a)
100
> (define b (power a 10))
> (time-function root b 10)
4968471029485769708957382910584867290793102859201859837486930281964323540987953617859603728190508050
8.471
> (define b (power a 20))
> (time-function root b 20)
4968471029485769708957382910584867290793102859201859837486930281964323540987953617859603728190508050
179.853
> (define b (power a 30))
> (time-function root b 30)
4968471029485769708957382910584867290793102859201859837486930281964323540987953617859603728190508050
1081.642
> (define b (power a 40))
> (time-function root b 40)
4968471029485769708957382910584867290793102859201859837486930281964323540987953617859603728190508050
3899.626
> (num-digits b)
3988
>

[REDEBOLT]

Hi Dan,

Your program has inspired me to write a program in TB using HIME:


Last Modified = 05-15-2011 at 20:21:06
Program = Roots
Roots of large numbers.
hi_Version 205

Base = 387
Exponent = 100
Num-digits = 259

Root # = 100
Root = 387
Remainder = 0
2.295 secs.

Base = 387
Exponent = 120
Num-digits = 311

Root # = 120
Root = 387
Remainder = 0
5.585 secs.

Base = 387
Exponent = 140
Num-digits = 363

Root # = 140
Root = 387
Remainder = 0
10.323 secs.

Base = 387
Exponent = 160
Num-digits = 415

Root # = 160
Root = 387
Remainder = 0
24.009 secs.

Base = 6857468364758627564768
Exponent = 11
Num-digits = 241

Root # = 11
Root = 6857468364758627564768
Remainder = 0
0.004 secs.

Base = 6857468364758627564768
Exponent = 22
Num-digits = 481

Root # = 22
Root = 6857468364758627564768
Remainder = 0
0.022 secs.

Base = 6857468364758627564768
Exponent = 28
Num-digits = 612

Root # = 28
Root = 6857468364758627564768
Remainder = 0
0.045 secs.

Base = 6857468364758627564768
Exponent = 32
Num-digits = 699

Root # = 32
Root = 6857468364758627564768
Remainder = 0
0.066 secs.

Base = 6857468364758627564768
Exponent = 36
Num-digits = 787

Root # = 36
Root = 6857468364758627564768
Remainder = 0
0.091 secs.

Base = 6857468364758627564768
Exponent = 40
Num-digits = 874

Root # = 40
Root = 6857468364758627564768
Remainder = 0
0.132 secs.

Base = 6857468364758627564768
Exponent = 51
Num-digits = 1114

Root # = 51
Root = 6857468364758627564768
Remainder = 0
0.317 secs.

Base = 18745070969977275018761
Exponent = 50
Num-digits = 1114

Root # = 50
Root = 18745070969977275018761
Remainder = 0
0.126 secs.

Base = 2607579665186594311711
Exponent = 52
Num-digits = 1114

Root # = 52
Root = 2607579665186594311711
Remainder = 0
0.124 secs.

Base = 64758365791029103867501928597010809643313974301243
Exponent = 1
Num-digits = 50

Root # = 1
Root = 64758365791029103867501928597010809643313974301243
Remainder = 0
0.000 secs.

Base = 64758365791029103867501928597010809643313974301243
Exponent = 10
Num-digits = 499

Root # = 10
Root = 64758365791029103867501928597010809643313974301243
Remainder = 0
0.003 secs.

Base = 64758365791029103867501928597010809643313974301243
Exponent = 20
Num-digits = 997

Root # = 20
Root = 64758365791029103867501928597010809643313974301243
Remainder = 0
0.015 secs.

Base = 64758365791029103867501928597010809643313974301243
Exponent = 30
Num-digits = 1495

Root # = 30
Root = 64758365791029103867501928597010809643313974301243
Remainder = 0
0.054 secs.

Base = 64758365791029103867501928597010809643313974301243
Exponent = 40
Num-digits = 1993

Root # = 40
Root = 64758365791029103867501928597010809643313974301243
Remainder = 0
0.196 secs.

Base = 64758365791029103867501928597010809643313974301243
Exponent = 53
Num-digits = 2640

Root # = 53
Root = 64758365791029103867501928597010809643313974301243
Remainder = 0
0.490 secs.

Base = 97
Exponent = 100
Num-digits = 199

Root # = 100
Root = 97
Remainder = 0
1.319 secs.

Base = 97
Exponent = 200
Num-digits = 398

Root # = 200
Root = 97
Remainder = 0
64.253 secs.

Base = 97
Exponent = 300
Num-digits = 597

Root # = 300
Root = 97
Remainder = 0
544.644 secs.

654.525 secs.

Done...
Press any key to end program.


Be sure to download the HIME freeware package from here (http://www.thinbasic.com/community/showthread.php?11156-H.i.m.e.).

The attached zip file contains the following files:

Roots2.tbasic - The HIME source program
root2.txt - The output results

[danbaron]

Wow, Bob, HIME destroys Racket.

And, you can use it from within thinBasic.

To me, it is amazingly fast.

I looked at the HIME website,

http://www.devotechs.com/ (http://www.devotechs.com/)

and I downloaded HIME.

It looks like a very high quality product.

And, it's relatively inexpensive.

Somehow, you found the author's complete name, Eddy Van Esch. I could only find, "Eddy".

The strange thing to me is that, the HIME forums effectively have zero activity.

That's hard for me to understand. I can only guess that this area is too specialized to generate activity/interest.

If so, then, that seems sad.

But, that doesn't reduce the value of his creation.

:unguee:

------------------------------------------------------

Time Comparisons

387^100
17.175 --> 2.295

387^120
47.190 --> 5.585

387^140
95.113 --> 10.323

387^160
177.044 --> 24.009

6857468364758627564768^11
0.187 --> 0.004

6857468364758627564768^22
5.850 --> 0.022

6857468364758627564768^28
20.028 --> 0.045

6857468364758627564768^32
33.384 --> 0.066

6857468364758627564768^36
55.162 --> 0.091

6857468364758627564768^40
86.689 --> 0.132

6857468364758627564768^51
261.783 --> 0.317

64758365791029103867501928597010809643313974301243^10
1.662 --> 0.003

64758365791029103867501928597010809643313974301243^20
36.572 --> 0.015

64758365791029103867501928597010809643313974301243^30
208.862 --> 0.054

64758365791029103867501928597010809643313974301243^40
756.792 --> 0.196

64758365791029103867501928597010809643313974301243^53
2746.575 --> 0.490

97^100
8.731 --> 1.319

97^200
268.261 --> 64.253

97^300
1866.335 --> 544.644

[Eddy Van Esch]

@Bob,

Nice work, Bob! Yes, there is lots of fun stuff that you can do with HIME :D. But then of course, I may be biased ... ;)

@Dan,

The strange thing to me is that, the HIME forums effectively have zero activity.

Yes, that is true. I set up the forum some time ago so that it can serve as a kind of knowledge base, so that I do not have to answer the same questions over and over again by e-mail. But somehow people seem to be more comfortable with just e-mailing me.
My forum is plagued regularly by bogus registrations by spambots (or whatever bots) so I have to approve forum registrations. Maybe that also brings people to just drop me a mail.
Anyway, if you have any kind of question about HIME, don't hesitate to send me an e-mail.
[support AT devotechs DOT com]

Kind regards
Eddy

[ErosOlmi]

Hi Eddy and welcome to thinBasic community forum.

I try my best to keeping this place clean from spammers and bots. So far I was able.
Hope you can take advance of this place to spread your library power even more.

Ciao
Eros

[Eddy Van Esch]

Thanks for the kind words, Eros.
It has been some time since I took a peek at ThinBasic, but it seems you have done a tremendous job! Well done!!

Kind regards
Eddy

[danbaron]

To me, it's funny.

At the top of this thread, for "Ads by Google", I saw links for "Root Canal", "Dandelion Root", and "Turmeric Root".

I guess Google is not perfect, --> yet.

(We probably have a couple more months.)

:?:

[REDEBOLT]

Wow, Bob, HIME destroys Racket.

And, you can use it from within thinBasic.

To me, it is amazingly fast.



You can't compare apples to oranges, Dan. :) Racket is an interpreted langage whereas HIME is written in PowerBASIC and, I presume, assembly. High level languages allow you to write elegant programs that are small in size and quick to write. Great for one-time or seldom use. The lower level languages are good for fast execution and are compiled to machine code. Thinbasic is somewhere in between. Its interpreted yet very fast. For some programs, it is just as fast, and sometimes faster than compiled code. I find it a pleasure to use. And, of course, HIME is compiled code. So you have an interpreted program running compiled code. What a combination! :o

Kudos to Eros and the programming staff here at Thinbasic.com. They have done a marvelous job. :cool:

Edit: I just ran the program in PB. It took twice as long as TB.

Regards,
Bob

[danbaron]

Hi Bob.

I agree that speed is not all that matters.

But, it's fun to do comparisons anyway.

Too bad we don't have a common machine to do tests on, like a university computer. Maybe in the future.

So, as of now we have no way of determining how much execution speed differences, are due to the speed differences of the two machines.

(Racket is compiled into byte-code.)

I was able to squeeze out some more (seemingly, a lot more) speed by using Racket's built-in "expt" function, instead of the power function I previously made myself.

I tried other methods besides the bisection method I'm using, but, so far, they are all slower.

It seems that the cases in which Racket has the best chance against HIME, are when the base is small, and the exponent is big.

So, if you want to, and you get the chance, run the cases below with thinBasic and HIME, and then, post your results.

(Again, all of the times shown, are in seconds.)

:twisted:


' code -----------------------------------------------------------------------------------------------

#lang racket

(define (root x n)
(define below 0)
(define above x)
(define (loop)
(define r (round (/ (+ below above) 2)))
(define p (expt r n))
(cond
((<= (- above below) 1) below)
((<= p x)
(set! below r)
(loop))
(else
(set! above r)
(loop))))
(cond
((= n 0) #f)
((= x 1) 1)
((= n 1) x)
(else
(loop))))

(define (time-root x n)
(let ((t1 (current-milliseconds)))
(let ((result (root x n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values result tt))))))

' REPL interactions ----------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define a (expt 3 100))
> (time-root a 100)
3
0.044
> (define a (expt 3 200))
> (time-root a 200)
3
0.8
> (define a (expt 3 300))
> (time-root a 300)
3
3.79
> (define a (expt 3 400))
> (time-root a 400)
3
11.376
> (define a (expt 3 500))
> (time-root a 500)
3
28.248
> (define a (expt 3 600))
> (time-root a 600)
3
57.134
> (define a (expt 3 700))
> (time-root a 700)
3
106.635
> (define a (expt 3 800))
> (time-root a 800)
3
177.11
> (define a (expt 3 900))
> (time-root a 900)
3
292.791
> (define a (expt 3 1000))
> (time-root a 1000)
3
452.356
>

[danbaron]

New Time Comparisons (with adjustment to Racket procedure)

(Racket --> HIME)

387^100
3.198 --> 2.295

387^120
6.536 --> 5.585

387^140
12.137 --> 10.323

387^160
19.968 --> 24.009

6857468364758627564768^11
0.109 --> 0.004

6857468364758627564768^22
1.841 --> 0.022

6857468364758627564768^28
4.430 --> 0.045

6857468364758627564768^32
6.864 --> 0.066

6857468364758627564768^36
11.279 --> 0.091

6857468364758627564768^40
16.989 --> 0.132

6857468364758627564768^51
57.517 --> 0.317

64758365791029103867501928597010809643313974301243^10
0.702 --> 0.003

64758365791029103867501928597010809643313974301243^20
8.643 --> 0.015

64758365791029103867501928597010809643313974301243^30
47.923 --> 0.054

64758365791029103867501928597010809643313974301243^40
128.170 --> 0.196

64758365791029103867501928597010809643313974301243^53
489.794 --> 0.490

97^100
3.027 --> 1.319

97^200
24.710 --> 64.253

97^300
126.360 --> 544.644


' REPL interactions ---------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define a (expt 387 100))
> (time-root a 100)
387
3.198
> (define a (expt 387 120))
> (time-root a 120)
387
6.536
> (define a (expt 387 140))
> (time-root a 140)
387
12.137
> (define a (expt 387 160))
> (time-root a 160)
387
19.968
> (define a 6857468364758627564768)
> (define b (expt a 11))
> (time-root b 11)
6857468364758627564768
0.109
> (define b (expt a 22))
> (time-root b 22)
6857468364758627564768
1.841
> (define b (expt a 28))
> (time-root b 28)
6857468364758627564768
4.43
> (define b (expt a 32))
> (time-root b 32)
6857468364758627564768
6.864
> (define b (expt a 36))
> (time-root b 36)
6857468364758627564768
11.279
> (define b (expt a 40))
> (time-root b 40)
6857468364758627564768
16.989
> (define b (expt a 51))
> (time-root b 51)
6857468364758627564768
57.517
> (define a 64758365791029103867501928597010809643313974301243)
> (define b (expt a 10))
> (time-root b 10)
64758365791029103867501928597010809643313974301243
0.702
> (define b (expt a 20))
> (time-root b 20)
64758365791029103867501928597010809643313974301243
8.643
> (define b (expt a 30))
> (time-root b 30)
64758365791029103867501928597010809643313974301243
47.923
> (define b (expt a 40))
> (time-root b 40)
64758365791029103867501928597010809643313974301243
128.17
> (define b (expt a 53))
> (time-root b 53)
64758365791029103867501928597010809643313974301243
489.794
> (define a (expt 97 100))
> (time-root a 100)
97
3.027
> (define a (expt 97 200))
> (time-root a 200)
97
24.71
> (define a (expt 97 300))
> (time-root a 300)
97
126.36
>

[danbaron]

Latest Time Comparisons

I changed the Racket root procedure again.

This time, I apparently got the idea of what to do, because now, there is what seems to me to be, real speed.

(But, still, the times (in seconds) are for two different machines.)

:oops: :twisted:

comparisons -----------------------------------------------------------------------------------------------------

(Racket -- HIME)

387^100
0.000 -- 2.295

387^120
0.000 -- 5.585

387^140
0.000 -- 10.323

387^160
0.000 -- 24.009

6857468364758627564768^11
0.000 -- 0.004

6857468364758627564768^22
0.000 -- 0.022

6857468364758627564768^28
0.000 -- 0.045

6857468364758627564768^32
0.015 -- 0.066

6857468364758627564768^36
0.000 -- 0.091

6857468364758627564768^40
0.000 -- 0.132

6857468364758627564768^51
0.000 -- 0.317

64758365791029103867501928597010809643313974301243^10
0.000 -- 0.003

64758365791029103867501928597010809643313974301243^20
0.016 -- 0.015

64758365791029103867501928597010809643313974301243^30
0.015 -- 0.054

64758365791029103867501928597010809643313974301243^40
0.031 -- 0.196

64758365791029103867501928597010809643313974301243^53
0.046 -- 0.490

97^100
0.000 -- 1.319

97^200
0.000 -- 64.253

97^300
0.000 -- 544.644



' code ----------------------------------------------------------------------------------------------------------

#lang racket

(define (root x n)
(define (num-digits n)
(define ns (number->string n))
(define sl (string->list ns))
(length sl))
(define nd (num-digits x))
(define above (expt 10 (ceiling (/ nd n))))
(define below (/ above 10))
(define (loop)
(define r (round (/ (+ below above) 2)))
(define p (expt r n))
(cond
((<= (- above below) 1) below)
((<= p x)
(set! below r)
(loop))
(else
(set! above r)
(loop))))
(cond
((= n 0) #f)
((= x 1) 1)
((= n 1) x)
(else
(loop))))

(define (time-root x n)
(let ((t1 (current-milliseconds)))
(let ((result (root x n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values result tt))))))

' REPL interactions ---------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define a (expt 387 100))
> (time-root a 100)
387
0
> (define a (expt 387 120))
> (time-root a 120)
387
0
> (define a (expt 387 140))
> (time-root a 140)
387
0
> (define a (expt 387 160))
> (time-root a 160)
387
0
> (define a 6857468364758627564768)
> (define b (expt a 11))
> (time-root b 11)
6857468364758627564768
0
> (define b (expt a 22))
> (time-root b 22)
6857468364758627564768
0
> (define b (expt a 28))
> (time-root b 28)
6857468364758627564768
0
> (define b (expt a 32))
> (time-root b 32)
6857468364758627564768
0.015
> (define b (expt a 36))
> (time-root b 36)
6857468364758627564768
0
> (define b (expt a 40))
> (time-root b 40)
6857468364758627564768
0
> (define b (expt a 51))
> (time-root b 51)
6857468364758627564768
0
> (define a 64758365791029103867501928597010809643313974301243)
> (define b (expt a 10))
> (time-root b 10)
64758365791029103867501928597010809643313974301243
0
> (define b (expt a 20))
> (time-root b 20)
64758365791029103867501928597010809643313974301243
0.016
> (define b (expt a 30))
> (time-root b 30)
64758365791029103867501928597010809643313974301243
0.015
> (define b (expt a 40))
> (time-root b 40)
64758365791029103867501928597010809643313974301243
0.031
> (define b (expt a 53))
> (time-root b 53)
64758365791029103867501928597010809643313974301243
0.046
> (define a (expt 97 100))
> (time-root a 100)
97
0
> (define a (expt 97 200))
> (time-root a 200)
97
0
> (define a (expt 97 300))
> (time-root a 300)
97
0
>

[danbaron]

More Timings:

Here are some more root timings (in seconds).

:oops: :neutral:


Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define a (expt 3 1000))
> (time-root a 1000)
3
0
> (define a (expt 3 2000))
> (time-root a 2000)
3
0
> (define a (expt 3 4000))
> (time-root a 4000)
3
0
> (define a (expt 3 8000))
> (time-root a 8000)
3
0
> (define a (expt 3 16000))
> (time-root a 16000)
3
0.016
> (define a (expt 3 32000))
> (time-root a 32000)
3
0.015
> (define a (expt 3 64000))
> (time-root a 64000)
3
0.062
> (define a (expt 3 128000))
> (time-root a 128000)
3
0.218
> (define a (expt 3 256000))
> (time-root a 256000)
3
0.624
> (define a (expt 3 512000))
> (time-root a 512000)
3
1.856
> (define a (expt 3 1024000))
> (time-root a 1024000)
3
5.304
> (define a (expt 3 2048000))
> (time-root a 2048000)
3
14.414
> (define a (expt 3 4096000))
> (time-root a 4096000)
3
39.842
> (define a (expt 3 8192000))
> (time-root a 8192000)
3
114.816
> (num-digits a)
3908578
>

[REDEBOLT]

Here are the calculations. I had to stop them because they were taking too long. I think I will develop a different approach.

Last Modified = 05-18-2011 at 01:31:37
Program = Roots3
Roots of large numbers.
hi_Version 205

Base = 3
Exponent = 100
Num-digits = 48

Root # = 100
Root = 3
Remainder = 0
2.098 secs.

Base = 3
Exponent = 200
Num-digits = 96

Root # = 200
Root = 3
Remainder = 0
71.265 secs.

Base = 3
Exponent = 300
Num-digits = 144

Root # = 300
Root = 3
Remainder = 0
453.834 secs.

Base = 3
Exponent = 400
Num-digits = 191

Regards,
Bob

[danbaron]

Thanks for running the tests, Bob.

Here are a few more timings.

I'm just about "out of gas" for this topic, unless I can find a way to make the root procedure faster.

Below, nothing of consequence is changed in the code.

I moved the "num-digits" procedure back out of the "root" procedure.

I made a little procedure, "x^x", which calculates x^x.

Three roots are calculated:

The 975319th root of 975319^975319,

The 975320th root of 975319^975319,

The 975318th root of 975319^975319.

Maybe, calculating the xth root of x^x is the best test of a root procedure.

Then, the base and the exponent are (obviously) equal.

Dan


' code ----------------------------------------------------------------------------------------------------------------

#lang racket

(define (x^x x)
(expt x x))

(define (num-digits n)
(define ns (number->string n))
(define sl (string->list ns))
(length sl))

(define (root x n)
(define nd (num-digits x))
(define above (expt 10 (ceiling (/ nd n))))
(define below (/ above 10))
(define (loop)
(define r (round (/ (+ below above) 2)))
(define p (expt r n))
(cond
((<= (- above below) 1) below)
((<= p x)
(set! below r)
(loop))
(else
(set! above r)
(loop))))
(cond
((= n 0) #f)
((= x 1) 1)
((= n 1) x)
(else
(loop))))

(define (time-root x n)
(let ((t1 (current-milliseconds)))
(let ((result (root x n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values result tt))))))

' REPL interactions ---------------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define a 975319)
> (define b (x^x a))
> (num-digits b)
5841329
> (time-root b a)
975319
785.414
> (time-root b (+ a 1))
975305
788.185
> (time-root b (- a 1))
975332
771.534
>

[danbaron]

I got a little more speed, by substituting the procedure, "num-digits-2", for, "num-digits", in the root procedure.

The same three roots are calculated (all times in seconds):

The 975319th root of 975319^975319,

The 975320th root of 975319^975319,

The 975318th root of 975319^975319.

And, there are some revised and additional base 3 root times.

:idea:


' code ----------------------------------------------------------------------------------------------------------------

#lang racket

(define (x^x x)
(expt x x))

(define (num-digits-2 n)
(define x (/ (log n) (log 10)))
(define y (ceiling x))
(when (= x y) (set! y (+ y 1)))
(inexact->exact y))

(define (root x n)
(define nd (num-digits-2 x))
(define above (expt 10 (ceiling (/ nd n))))
(define below (/ above 10))
(define (loop)
(define r (round (/ (+ below above) 2)))
(define p (expt r n))
(cond
((<= (- above below) 1) below)
((<= p x)
(set! below r)
(loop))
(else
(set! above r)
(loop))))
(cond
((= n 0) #f)
((= x 1) 1)
((= n 1) x)
(else
(loop))))

(define (time-root x n)
(let ((t1 (current-milliseconds)))
(let ((result (root x n)))
(let ((t2 (current-milliseconds)))
(let ((tt (/ (- t2 t1) 1000.0)))
(values result tt))))))

' REPL interactions ---------------------------------------------------------------------------------------------------

Welcome to DrRacket, version 5.1 [3m].
Language: racket.
> (define a 975319)
> (define b (x^x a))
> (time-root b a)
975319
594.934
> (time-root b (+ a 1))
975305
526.59
> (time-root b (- a 1))
975332
525.16

> (define a (expt 3 8192000))
> (time-root a 8192000)
3
61.729
> (define a (expt 3 16384000))
> (time-root a 16384000)
3
150.805
> (define a (expt 3 32768000))
> (time-root a 32768000)
3
414.383
> (num-digits-2 a)
15634310
>