Hi!
I wrote a very short program that puts a number into a humangous power
and finding its last 6 digits. The formula is to devide the power by 2
if it's an even number and square the number i need to put into that
humangous power. So 2 to the power of 100, is the same as 2 to the
power of 2 to the power of 50, etc... When it's done i have to devide
it by 100000 and get remainder to find last 6 digits. The idea is very
simple. This way it should not take long. However my program never
finishes running. It's literally 10 lines long. Can you please take a
look at it? Thank you very much!
(define p 647307989872865201422284359961937038113215496061434545237)
(define (square y)
(* y y))
(define (Last6Digits b x)
(remainder (fast_power b x) 1000000))
(define (fast_power a p)
(cond ((= p 0) 1)
((= p 1) a)
((even? p)(fast_power(square a)(/ p 2)))
(else (* a (fast_power a (- p 1))))))
I will appreciate any ideas. Thanks.
-sergey-
In article <·················@ix.netcom.com>,
Yuriy Tenenbaum <······@ix.netcom.com> wrote:
>Hi!
>
>I wrote a very short program that puts a number into a humangous power
>and finding its last 6 digits. The formula is to devide the power by 2
>if it's an even number and square the number i need to put into that
>humangous power. So 2 to the power of 100, is the same as 2 to the
>power of 2 to the power of 50, etc... When it's done i have to devide
>it by 100000 and get remainder to find last 6 digits. The idea is very
>simple. This way it should not take long. However my program never
>finishes running. It's literally 10 lines long. Can you please take a
>look at it? Thank you very much!
The running time will be very dependent on the values you're supplying. If
you're giving it large numbers, you'll do quite a bit of bignum arithmetic
on really large numbers, which can be pretty slow. What parameters are you
using?
>(define p 647307989872865201422284359961937038113215496061434545237)
This doesn't seem to be used anywhere -- what's it for?
The rest of your code looks fine to me.
>(define (square y)
> (* y y))
>
>(define (Last6Digits b x)
> (remainder (fast_power b x) 1000000))
>
>(define (fast_power a p)
> (cond ((= p 0) 1)
> ((= p 1) a)
> ((even? p)(fast_power(square a)(/ p 2)))
> (else (* a (fast_power a (- p 1))))))
>
>
>
>I will appreciate any ideas. Thanks.
>
>-sergey-
>
>
--
Barry Margolin, ······@bbnplanet.com
GTE Internetworking, Powered by BBN, Burlington, MA
*** DON'T SEND TECHNICAL QUESTIONS DIRECTLY TO ME, post them to newsgroups.
Please DON'T copy followups to me -- I'll assume it wasn't posted to the group.
Yuriy Tenenbaum <······@ix.netcom.com> writes:
> Hi!
>
> I wrote a very short program that puts a number into a humangous power
> and finding its last 6 digits. The formula is to devide the power by 2
> if it's an even number and square the number i need to put into that
> humangous power. So 2 to the power of 100, is the same as 2 to the
> power of 2 to the power of 50, etc... When it's done i have to devide
> it by 100000 and get remainder to find last 6 digits. The idea is very
> simple. This way it should not take long. However my program never
> finishes running. It's literally 10 lines long. Can you please take a
> look at it? Thank you very much!
Hint: (a * b) mod r == ((a mod r) * (b mod r)) mod r
(defun modmul (a b r)
(mod (* a b) r))
(defun modpower (b x r)
(cond ((= x 0) 1)
((= x 1) b)
((evenp x) (modpower (modmul b b r) (/ x 2) r))
(t (modmul b (modpower b (1- x) r) r))))
Not that it seems to matter much for Allegro Common Lisp (for
this problem size :-)
USER(30): *p*
647307989872865201422284359961937038113215496061434545237
USER(31): (time (mod (expt *p* 100) 100000))
; cpu time (non-gc) 47 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 47 msec user, 0 msec system
; real time 45 msec
; space allocation:
; 4 cons cells, 0 symbols, 13,576 other bytes, 0 static bytes
94001
USER(32): (time (modpower *p* 100 100000))
; cpu time (non-gc) 8 msec user, 0 msec system
; cpu time (gc) 0 msec user, 0 msec system
; cpu time (total) 8 msec user, 0 msec system
; real time 1 msec
; space allocation:
; 277 cons cells, 0 symbols, 1,272 other bytes, 0 static bytes
94001
--
Raymond Wiker, Orion Systems AS
+47 370 61150