Rosetta Code

Cipolla's algorithm: Difference between revisions

Page Discussion

Cipolla's algorithm (view source)

Revision as of 23:03, 30 August 2022

37 bytes added ,  1 year ago
m
Automated syntax highlighting fixup (second round - minor fixes)
m (syntax highlighting fixup automation)
m (Automated syntax highlighting fixup (second round - minor fixes))
Line 75:
* [[Tonelli-Shanks algorithm]]
<br><br>
 
=={{header|11l}}==
{{trans|Python}}
 
<syntaxhighlight lang="11l">F convertToBase(n, b)
I (n < 2)
R [n]
Line 135 ⟶ 134:
Roots of 8219 mod 10007: []
</pre>
 
=={{header|C}}==
{{trans|FreeBasic}}
<syntaxhighlight lang="c">#include <stdbool.h>
#include <stdint.h>
#include <stdio.h>
Line 346 ⟶ 344:
Find solution for n = 665165880 and p = 1000000007
Solution found: x1 = 524868305, x2 = 475131702</pre>
 
=={{header|C sharp|C#}}==
<syntaxhighlight lang="csharp">using System;
using System.Numerics;
 
Line 434 ⟶ 431:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
 
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang=D"d">import std.bigint;
import std.stdio;
import std.typecons;
Line 530 ⟶ 526:
Tuple!(BigInt, "x", BigInt, "y", bool, "b")(791399408049, 208600591990, true)
Tuple!(BigInt, "x", BigInt, "y", bool, "b")(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>
 
=={{header|EchoLisp}}==
<syntaxhighlight lang="scheme">
(lib 'struct)
(lib 'types)
Line 605 ⟶ 600:
 
</pre>
 
=={{header|F_Sharp|F#}}==
===The function===
This task uses [http://www.rosettacode.org/wiki/Extensible_prime_generator#The_function Extensible Prime Generator (F#)]
<syntaxhighlight lang="fsharp">
// Cipolla's algorithm. Nigel Galloway: June 16th., 2019
let Cipolla n g =
Line 623 ⟶ 617:
</syntaxhighlight>
===The Task===
<syntaxhighlight lang="fsharp">
let test=[(10I,13I);(56I,101I);(8218I,10007I);(8219I,10007I);(331575I,1000003I);(665165880I,1000000007I);(881398088036I,1000000000039I);(34035243914635549601583369544560650254325084643201I,10I**50+151I)]
test|>List.iter(fun(n,g)->match Cipolla n g with Some r->printfn "Cipolla %A %A -> %A (%A) check %A" n g r (g-r) ((r*r)%g) |_->printfn "Cipolla %A %A -> has no result" n g)
Line 639 ⟶ 633:
Real: 00:00:00.089, CPU: 00:00:00.090, GC gen0: 2, gen1: 0
</pre>
 
=={{header|Factor}}==
{{trans|Sidef}}
{{works with|Factor|0.99 2020-08-14}}
<syntaxhighlight lang="factor">USING: accessors assocs interpolate io kernel literals locals
math math.extras math.functions ;
 
Line 705 ⟶ 698:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151
</pre>
 
=={{header|FreeBASIC}}==
===LongInt version===
Had a close look at the EchoLisp code for step 2.
Used the FreeBASIC code from the Miller-Rabin task for prime testing.
<syntaxhighlight lang="freebasic">' version 08-04-2017
' compile with: fbc -s console
' maximum for p is 17 digits to be on the save side
Line 920 ⟶ 912:
===GMP version===
{{libheader|GMP}}
<syntaxhighlight lang="freebasic">' version 12-04-2017
' compile with: fbc -s console
 
Line 1,092 ⟶ 1,084:
Find solution for n = 34035243914635549601583369544560650254325084643201 and p = 10^50 + 151
Solution found: x1 = 17436881171909637738621006042549786426312886309400, x2 = 82563118828090362261378993957450213573687113690751</pre>
 
=={{header|Go}}==
===int===
Implementation following the pseudocode in the task description.
<syntaxhighlight lang="go">package main
 
import "fmt"
Line 1,169 ⟶ 1,160:
===big.Int===
Extra credit:
<syntaxhighlight lang="go">package main
 
import (
Line 1,236 ⟶ 1,227:
17436881171909637738621006042549786426312886309400
</pre>
 
=={{header|J}}==
 
Based on the echolisp implementation:
 
<syntaxhighlight lang=J"j">leg=: dyad define
x (y&|)@^ (y-1)%2
)
Line 1,278 ⟶ 1,268:
Task examples:
 
<syntaxhighlight lang=J"j"> 10 cipolla 13
6 7
56 cipolla 101
Line 1,295 ⟶ 1,285:
34035243914635549601583369544560650254325084643201x cipolla (10^50x) + 151
17436881171909637738621006042549786426312886309400 82563118828090362261378993957450213573687113690751</syntaxhighlight>
 
=={{header|Java}}==
{{trans|Kotlin}}
{{works with|Java|8}}
<syntaxhighlight lang=Java"java">import java.math.BigInteger;
import java.util.function.BiFunction;
import java.util.function.Function;
Line 1,416 ⟶ 1,405:
(791399408049, 208600591990, true)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)</pre>
 
=={{header|jq}}==
{{trans|Wren}}
Line 1,422 ⟶ 1,410:
 
A Point is represented by a numeric array of length two (i.e. [x,y]).
<syntaxhighlight lang="jq"># To take advantage of gojq's arbitrary-precision integer arithmetic:
def power($b): . as $in | reduce range(0;$b) as $i (1; . * $in);
 
Line 1,511 ⟶ 1,499:
[82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,true]
</pre>
 
 
=={{header|Julia}}==
{{trans|Perl}}
<syntaxhighlight lang="julia">using Primes
 
function legendre(n, p)
Line 1,572 ⟶ 1,558:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151.
</pre>
 
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight lang="scala">// version 1.2.0
 
import java.math.BigInteger
Line 1,654 ⟶ 1,639:
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true)
</pre>
 
=={{header|Mathematica}}/{{header|Wolfram Language}}==
<syntaxhighlight lang=Mathematica"mathematica">ClearAll[Cipolla]
Cipolla[n_, p_] := Module[{ls, omega2, nn, a, r, s},
ls = JacobiSymbol[n, p];
Line 1,704 ⟶ 1,688:
{791399408049,208600591990,True}
{82563118828090362261378993957450213573687113690751,17436881171909637738621006042549786426312886309400,True}</pre>
 
=={{header|Nim}}==
{{trans|Kotlin}}
{{libheader|bignum}}
<syntaxhighlight lang=Nim"nim">import options
import bignum
 
Line 1,798 ⟶ 1,781:
(791399408049, 208600591990)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400)</pre>
 
=={{header|Perl}}==
{{trans|Raku}}
{{libheader|ntheory}}
<syntaxhighlight lang="perl">use bigint;
use ntheory qw(is_prime);
 
Line 1,861 ⟶ 1,843:
Roots of 665165880 are (475131702, 524868305) mod 1000000007
Roots of 881398088036 are (791399408049, 208600591990) mod 1000000000039</pre>
 
=={{header|Phix}}==
{{trans|Kotlin}}
{{libheader|Phix/mpfr}}
<!--<syntaxhighlight lang=Phix"phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span>
Line 1,974 ⟶ 1,955:
{"82563118828090362261378993957450213573687113690751","17436881171909637738621006042549786426312886309400","true"}}
</pre>
 
=={{header|PicoLisp}}==
{{trans|Go}}
<syntaxhighlight lang=PicoLisp"picolisp"># from @lib/rsa.l
(de **Mod (X Y N)
(let M 1
Line 2,049 ⟶ 2,029:
(82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400)
</pre>
 
=={{header|Python}}==
<syntaxhighlight lang="python">
#Converts n to base b as a list of integers between 0 and b-1
#Most-significant digit on the left
Line 2,111 ⟶ 2,090:
Roots of 8219 mod 10007: ()
</pre>
 
=={{header|Racket}}==
{{trans|EchoLisp}}
 
<syntaxhighlight lang="racket">#lang racket
 
(require math/number-theory)
Line 2,200 ⟶ 2,178:
Roots of 881398088036 are (208600591990,791399408049) (mod 1000000000039)
Roots of 34035243914635549601583369544560650254325084643201 are (17436881171909637738621006042549786426312886309400,82563118828090362261378993957450213573687113690751) (mod 100000000000000000000000000000000000000000000000151)</pre>
 
=={{header|Raku}}==
(formerly Perl 6)
Line 2,206 ⟶ 2,183:
{{trans|Sidef}}
 
<syntaxhighlight lang="raku" line># Legendre operator (𝑛│𝑝)
sub infix:<│> (Int \𝑛, Int \𝑝 where 𝑝.is-prime && (𝑝 != 2)) {
given 𝑛.expmod( (𝑝-1) div 2, 𝑝 ) {
Line 2,277 ⟶ 2,254:
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151
</pre>
 
=={{header|Sage}}==
{{works with|Sage|7.6}}
<syntaxhighlight lang="sage">
def eulerCriterion(a, p):
return -1 if pow(a, int((p-1)/2), p) == p-1 else 1
Line 2,349 ⟶ 2,325:
False
</pre>
 
=={{header|Scala}}==
===Imperative solution===
<syntaxhighlight lang=Scala"scala">object CipollasAlgorithm extends App {
private val BIG = BigInt(10).pow(50) + BigInt(151)
 
Line 2,407 ⟶ 2,382:
}</syntaxhighlight>
{{Out}}See it running in your browser by [https://scalafiddle.io/sf/QQBsMza/3 ScalaFiddle (JavaScript, non JVM)] or by [https://scastie.scala-lang.org/NEP5hOWmSBqqpwmF30LpUA Scastie (JVM)].
 
=={{header|Sidef}}==
{{trans|Go}}
<syntaxhighlight lang="ruby">func cipolla(n, p) {
 
legendre(n, p) == 1 || return nil
Line 2,468 ⟶ 2,442:
Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151</pre>
 
=={{header|Visual Basic .NET}}==
{{trans|C#}}
<syntaxhighlight lang="vbnet">Imports System.Numerics
 
Module Module1
Line 2,552 ⟶ 2,525:
(791399408049, 208600591990, True)
(82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, True)</pre>
 
=={{header|Wren}}==
{{trans|Kotlin}}
{{libheader|Wren-big}}
{{libheader|Wren-dynamic}}
<syntaxhighlight lang="ecmascript">import "/big" for BigInt
import "/dynamic" for Tuple
 
Line 2,628 ⟶ 2,600:
[82563118828090362261378993957450213573687113690751, 17436881171909637738621006042549786426312886309400, true]
</pre>
 
=={{header|zkl}}==
{{trans|EchoLisp}}
Uses lib GMP (GNU MP Bignum Library).
<syntaxhighlight lang="zkl">var [const] BN=Import("zklBigNum"); //libGMP
fcn modEq(a,b,p) { (a-b)%p==0 }
fcn Legendre(a,p){ a.powm((p - 1)/2,p) }
Line 2,663 ⟶ 2,634:
return(x,(p-x)%p);
}</syntaxhighlight>
<syntaxhighlight lang="zkl">foreach n,p in (T(
T(10,13),T(56,101),T(8218,10007),T(8219,10007),T(331575,1000003),
T(665165880,1000000007),T(881398088036,1000000000039),
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/329265"