Pollard-rho algorithm in Haskell/OCaml/F#/Common Lisp/Gauche Scheme/Typed Racket/Erlang

gistfile1.txt

$ lsb_release -a
No LSB modules are available.
Distributor ID:	Ubuntu
Description:	Ubuntu 22.04.3 LTS
Release:	22.04
Codename:	jammy

$ grep "processor\|model name" /proc/cpuinfo
processor	: 0
model name	: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
processor	: 1
model name	: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
processor	: 2
model name	: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz
processor	: 3
model name	: Intel(R) Core(TM) i7-10710U CPU @ 1.10GHz

$ python3 --version
Python 3.10.12

$ ghc --version
The Glorious Glasgow Haskell Compilation System, version 9.2.8

$ ocamlopt --version
4.13.1

$ dotnet --version
7.0.110

$ sbcl --version
SBCL 2.1.11.debian

$ gosh -V
Gauche scheme shell, version 0.9.12 [utf-8,pthreads], x86_64-pc-linux-gnu
(version "0.9.12")
(command "gosh")
(scheme.id gauche)
(languages scheme r5rs r7rs)
(encodings utf-8)
(website "https://practical-scheme.net/gauche")
(build.platform "x86_64-pc-linux-gnu")
(build.configure "--prefix=/usr/local" "--enable-multibyte=utf-8")
(scheme.path "/usr/local/share/gauche-0.98/site/lib" "/usr/local/share/gauche-0.98/0.9.12/lib")
(gauche.threads pthreads)
(gauche.net.tls)

$ ./racket/bin/racket --version
Welcome to Racket v8.10 [cs].

$ erl -version
Erlang (SMP,ASYNC_THREADS) (BEAM) emulator version 12.2.1

$ ghc -O2 -o haskell PollardRho.hs

$ ocamlfind ocamlopt -O2 -o ocaml -linkpkg -package zarith Pollard_rho.ml

$ cd fsharp/
$ dotnet publish -c Release
$ cd ..

$ sbcl --script pollard-rho.cl

$ gosh build-standalone -o gauche pollard-rho.scm

$ ./racket/bin/raco exe --orig-exe -o typed-racket pollard-rho.rkt

$ time python3 pollard_rho.py 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m14.679s
user	0m14.662s
sys	0m0.009s

$ time ./haskell 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m6.300s
user	0m6.286s
sys	0m0.012s

$ time ./ocaml 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m5.547s
user	0m5.539s
sys	0m0.005s

$ time ./fsharp/bin/Release/net7.0/publish/fsharp 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m14.156s
user	0m14.147s
sys	0m0.037s

$ time ./common-lisp 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m38.043s
user	0m37.861s
sys	0m0.141s

$ time ./gauche 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	1m50.042s
user	2m9.899s
sys	0m8.852s

$ time ./typed-racket 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m29.163s
user	0m28.976s
sys	0m0.176s

$ time escript pollard_rho.erl 60766145992321225002169406923
60766145992321225002169406923 = 250117558771727 * 242950340194949

real	0m30.620s
user	0m30.449s
sys	0m0.161s

pollard-rho.cl

;; single-line comments

#|
multi-line comments
|#

(declaim (optimize (speed 3) (debug 0) (safety 0)))

(defun pollard-rho (n)
  (labels
    ((g (x)
       (mod (+ (* x x) 1) n))
     (f (x y d)
       (cond
         ((= d 1) (let* ((x2 (g x))
                         (y2 (g (g y)))
                         (d2 (gcd (abs (- x2 y2)) n)))
                    (f x2 y2 d2)))
         ((/= d n) d)
         (t nil))))
    (f 2 2 1)))

(defun main ()
  (let* ((args *posix-argv*)
         (n (parse-integer (second args)))
         (p (pollard-rho n)))
    (if p
        (format t "~a = ~a * ~a~%" n p (/ n p))
      (format t "~a is prime~%" n))))

#|
(main)
|#

(sb-ext:save-lisp-and-die "common-lisp"
                          :toplevel #'main
                          :executable t)

pollard-rho.rkt

#lang typed/racket

;; single-line comments

#|
multi-line comments
|#

(: pollard-rho (-> Integer (Option Integer)))
(define (pollard-rho n)
  (: g (-> Integer Integer))
  (define (g x)
    (modulo (+ (* x x) 1) n))
  (: f (-> Integer Integer Integer (Option Integer)))
  (define (f x y d)
    (cond
      ((= d 1) (let* ((x2 (g x))
                      (y2 (g (g y)))
                      (d2 (gcd (abs (- x2 y2)) n)))
                 (f x2 y2 d2)))
      ((not (= d n)) d)
      (else #f)))
  (f 2 2 1))

(: main (-> Void))
(define (main)
  (let* ((args (current-command-line-arguments))
         (n (string->number (vector-ref args 0)))
         (n (assert n exact-integer?))
         (p (pollard-rho n)))
    (if p
        (printf "~a = ~a * ~a~%" n p (/ n p))
      (printf "~a is prime~%" n))))

(main)

pollard-rho.scm

;; single-line comments

#|
multi-line comments
|#

(define (pollard-rho n)
  (define (g x)
    (mod (+ (* x x) 1) n))
  (define (f x y d)
    (cond
      ((= d 1) (let* ((x2 (g x))
                      (y2 (g (g y)))
                      (d2 (gcd (abs (- x2 y2)) n)))
                 (f x2 y2 d2)))
      ((not (= d n)) d)
      (else #f)))
  (f 2 2 1))

(define (main args)
  (let* ((n (string->number (list-ref args 1)))
         (p (pollard-rho n)))
    (if p
        (format #t "~a = ~a * ~a~%" n p (/ n p))
      (format #t "~a is prime~%" n)))
  0)

pollard_rho.erl

#!/usr/bin/env escript
%% -*- erlang -*-
%%! -sname pollard_rho -mnesia debug verbose
-mode(compile).

% single-line comments

gcd(A, 0) -> A;
gcd(A, B) -> gcd(B, A rem B).

g(N, X) -> (X*X + 1) rem N.

f(N, X, Y, 1) ->
  X2 = g(N, X),
  Y2 = g(N, g(N, Y)),
  D2 = gcd(abs(X2 - Y2), N),
  f(N, X2, Y2, D2);
f(N, _, _, D) ->
  if
    D /= N -> D;
    true -> []
  end.

pollard_rho(N) -> f(N, 2, 2, 1).

main([Arg]) ->
  N = list_to_integer(Arg),
  P = pollard_rho(N),
  if
    is_integer(P) -> io:format("~w = ~w * ~w\n", [N, P, N div P]);
    true -> io:format("~w is prime\n", [N])
  end.

Pollard_rho.ml

(*
$ sudo apt install libzarith-ocaml-dev

#use "topfind";;
#require "zarith";;
*)

(*
multi-line comments
*)

let pollard_rho n = Z.(
  let g x = (x*x + one) mod n in
  let rec f x y d =
    if d == one then
      let x' = g x in
      let y' = g (g y) in
      let d' = gcd (abs (x' - y')) n in
      f x' y' d'
    else if d != n then Some(d)
    else None in
  f ~$2 ~$2 ~$1
)

let () = Z.(
  let n = of_string Sys.argv.(1) in
  match pollard_rho n with
  | Some(p) -> Printf.printf "%a = %a * %a\n" output n output p output (n/p)
  | None    -> Printf.printf "%a is prime\n" output n
)

pollard_rho.py

import sys
from math import gcd

# single-line comments

"""
multi-line comments
"""

def pollard_rho(n: int) -> int | None:
    x, y, d = 2, 2, 1

    while d == 1:
        x = (x*x + 1) % n
        y = (y*y + 1) % n
        y = (y*y + 1) % n
        d = gcd(abs(x-y), n)

    if d != n:
        return d
    else:
        return None

if __name__ == '__main__':
    n = int(sys.argv[1])
    p = pollard_rho(n)
    if p:
        print('{} = {} * {}'.format(n, p, n//p))
    else:
        print('{} is prime'.format(n))

PollardRho.hs

import System.Environment
import Text.Printf

-- single-line comments

{-
multi-line comments
-}

pollardRho n =
  f 2 2 1
  where
    f x y 1 =
      let x' = g x
          y' = g (g y)
          d' = gcd (abs (x' - y')) n in
      f x' y' d'
    f x y d
      | n /= d    = Just d
      | otherwise = Nothing
    g x = (x*x + 1) `mod` n

main = do
  args <- getArgs
  let n = read (head args) :: Integer
  case pollardRho n of
    Just p  -> printf "%v = %v * %v\n" n p (n `div` p)
    Nothing -> printf "%v is prime\n" n

Program.fs

open System.Numerics

// single-line comments

(*
multi-line comments
*)

let pollardRho n =
  let inline g x = (x*x + 1I) % n
  let rec f x y d =
    if d = 1I then
      let x' = g x
      let y' = g (g y)
      let d' = bigint.GreatestCommonDivisor(abs (x' - y'), n)
      f x' y' d'
    else if d <> n then Some(d)
    else None
  f 2I 2I 1I

[<EntryPoint>]
let main args =
  let n = bigint.Parse(args[0])
  match pollardRho n with
  | Some(p) -> printfn "%A = %A * %A" n p (n/p)
  | None    -> printfn "%A is prime" n
  0