Hello Peter,
Thanks for the reply. The elapsed timings for the program rho3rec are:
chicken 5.3.0: 33.6 secondsRacket v8.2 [cs] : 18.1 secondsDr Racket : 20.6
seconds (1 MB memory)
The program uses the Pollard rho algorithm to find a factor of 2^257 -1. The
program is highly recursive, but I have a non recursive version that has the
same timing as the above. I am using an AMD Ryzen 5600 cpu and 32 GB of main
memory.
I tried all of the csc options that appeared related to speed, and the maximum
improvement was 0.1 seconds.
The one option I did not get to work was -heap-size 1000M
where I varied the size from 1000M to 1M. In all cases I would get the run
time message[panic] out of memory - heap full - execution terminated
I have include the program listing below and also as an attachment.
Regards,Doug
;#lang
racket ;; uncomment for racket
(define (rho n u v c iter prod) (let* ( [u1 (modulo (+ (* u u) c) n)]
[v1 (modulo (+ (* v v) c) n)] [v2 (modulo (+ (* v1 v1) c) n)]
[done #f] [max_iter 3000] [iter2 (+ iter 1)]
[prod2 (modulo (* prod (- u1 v2)) n)] )
(if (= (modulo iter2 150) 0) (begin ; modulo true (let ( [g
(gcd prod2 n) ] ) (if (and (> g 1) (< g n)) (begin ; factor
(display "factor = ") (display g) (newline) (display
"iterations = ") (display iter2) (newline) (set! done #t)
) (set! prod2 1) ; no factor ) ; end if factor ) ;
end let ) ; end begin for modulo true #f ;action for modulo false
) ; end major if
(if (and (< iter2 max_iter) (not done)) (rho n u1 v2 c iter2 prod2)
(if done ; either found factor or max iterations (display "normal
termination \n") #f ) ; if done ) ; if and ) ; end let*)
(let ( [n (- (expt 2 257) 1)] [u 2] [v 11] [c 7] [iter 1] [prod 1] )
(display "factor n = ") (display n) (newline) (time (rho n u v c iter prod)))
;;;
On Tuesday, May 21, 2024 at 12:13:55 AM MDT, Peter Bex
wrote:
(sending again, forgot to CC the users list)
On Mon, May 20, 2024 at 03:23:54PM +, T.D. Telford wrote:
> With the csc compiler and the -f or -fixnum-arithmetic option (Assume all
> numbers are fixnums) my benchmarks appear to be quite fast compared to racket
> of chez scheme. When running a benchmark that uses big integers (such as the
> pollard rho), execution times are almost twice as long as racket or chez.
Hello there!
When we initially added bignum support in core (it used to be an egg),
we spent quite a bit of effort optimizing various benchmarks, and
on several of these (but not all of course), at the end CHICKEN
performed *better* than several other Schemes, including Racket (which
wasn't Chez-based at the time). It's quite possible that Chez Scheme
has some optimized routines that other Schemes don't have, which we
could learn from.
If you have a specific benchmark that's slow, it would be helpful if you
could share the code so we can have a look what it is exactly that slows
things down.
> Is there an egg or alternate code to improve the efficiency of big integers?
> I would have thought there would be interface to gmp.
While GMP is optimized to the hilt, it won't necessarily improve speed.
The original "numbers" egg which provided add-on support for bignums
was based on GMP and slow as molasses. Mediocre numeric code that's
deeply integrated with the garbage collector and compilation strategy
can easily outperform supremely bummed code that has to go through the
FFI on every call.
Again, if you can share some benchmarking code we can have a look if
there are any obvious bottlenecks.
Cheers,
Peter
;; recursive
;;#lang racket;; uncomment for racket
(define (rho n u v c iter prod)
(let* ( [u1 (modulo (+ (* u u) c) n)]
[v1 (modulo (+ (* v v) c) n)]
[v2 (modulo (+ (* v1 v1) c) n)]
[done #f]
[max_iter 3000]
[iter2 (+ iter 1)]
[prod2 (modulo (* prod (- u1 v2)) n)] )
(if (= (modulo iter2 150) 0)
(begin; modulo true
(let ( [g (gcd prod2 n) ] )
(if (and (> g 1) (< g n))
(begin ; factor
(display "factor = ") (display g) (newline)
(display "iterations = ") (display iter2) (newline)
(set! done #t)
)
(set! prod2 1) ; no factor
) ; end if factor
) ; end let
) ; end begin for modulo true
#f ;action for modulo false
) ; end major if
(if (and (< iter2 max_iter) (not done))
(rho n u1 v2 c iter2 prod2)
(if done ; either found factor or max iterations
(display "normal termination \n")
#f
