Cipolla's algorithm: Difference between revisions

</pre>

=={{header|F_Sharp|F#}}==

===The function===

This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]

<lang fsharp>

// Cipolla's algorithm. Nigel Galloway: June 16th., 2019

let Cipolla n g =

let rec fN i g e l=match e with n when n=0I->i |_ when e%2I=1I->fN ((i*g)%l) ((g*g)%l) (e/2I) l |_-> fN i ((g*g)%l) (e/2I) l

let rec fG g=match (n/g+g)>>>1 with n when bigint.Abs(g-n)>>>1<2I->n+1I |g->fG g

let a,b=let rec fI i=let q=i*i-n in if fN 1I q ((g-1I)/2I) g>1I then (i,q) else fI (i+1I) in fI(fG (bigint(sqrt(double n))))

let fE=Seq.unfold(fun(n,i)->Some((n,i),((n*n+i*i*b)%g,(2I*n*i)%g)))(a,1I)|>Seq.cache

let rec fL Πn Πi α β=match 2I**α with

Ω when Ω<β->fL Πn Πi (α+1) β

|Ω when Ω>β->let n,i=Seq.item (α-1) fE in fL ((Πn*n+Πi*i*b)%g) ((Πn*i+Πi*n)%g) 0 (β-Ω/2I)

|_->let n,i=Seq.item α fE in ((Πn*n+Πi*i*b)%g)

if fN 1I n ((g-1I)/2I) g<>1I then None else Some(fL 1I 0I 0 ((g+1I)/2I))

</lang>

{{out}}

<pre>

Cipolla 10 13 -> 7 (6) check 10

Cipolla 56 101 -> 64 (37) check 56

Cipolla 8218 10007 -> 135 (9872) check 8218

Cipolla 8219 10007 -> has no result

Cipolla 331575 1000003 -> 144161 (855842) check 331575

Cipolla 665165880 1000000007 -> 475131702 (524868305) check 665165880

Cipolla 881398088036 1000000000039 -> 208600591990 (791399408049) check 881398088036

Cipolla 34035243914635549601583369544560650254325084643201 100000000000000000000000000000000000000000000000151 -> 17436881171909637738621006042549786426312886309400 (82563118828090362261378993957450213573687113690751) check 34035243914635549601583369544560650254325084643201

Real: 00:00:00.089, CPU: 00:00:00.090, GC gen0: 2, gen1: 0