Cipolla's algorithm: Difference between revisions
Content added Content deleted
(Added Wren) |
(Add Factor) |
||
| Line 578: | Line 578: | ||
Cipolla 34035243914635549601583369544560650254325084643201 100000000000000000000000000000000000000000000000151 -> 17436881171909637738621006042549786426312886309400 (82563118828090362261378993957450213573687113690751) check 34035243914635549601583369544560650254325084643201 |
Cipolla 34035243914635549601583369544560650254325084643201 100000000000000000000000000000000000000000000000151 -> 17436881171909637738621006042549786426312886309400 (82563118828090362261378993957450213573687113690751) check 34035243914635549601583369544560650254325084643201 |
||
Real: 00:00:00.089, CPU: 00:00:00.090, GC gen0: 2, gen1: 0 |
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}} |
|||
<lang factor>USING: accessors assocs interpolate io kernel literals locals |
|||
math math.extras math.functions ; |
|||
IN: rosetta-code.cipolla |
|||
TUPLE: point x y ; |
|||
C: <point> point |
|||
:: (cipolla) ( n p -- m ) |
|||
0 0 :> ( a! ω2! ) |
|||
[ ω2 p legendere -1 = ] |
|||
[ a sq n - p rem ω2! a 1 + a! ] do until a 1 - a! |
|||
[| a b | |
|||
a x>> b x>> * a y>> b y>> ω2 * * + p mod |
|||
a x>> b y>> * b x>> a y>> * + p mod <point> |
|||
] :> [mul] |
|||
1 0 <point> :> r! |
|||
a 1 <point> :> s! |
|||
p 1 + -1 shift :> n! |
|||
[ n 0 > ] [ |
|||
n odd? [ r s [mul] call r! ] when |
|||
s s [mul] call s! |
|||
n -1 shift n! |
|||
] while |
|||
r y>> zero? r x>> f ? ; |
|||
: cipolla ( n p -- m/f ) |
|||
2dup legendere 1 = [ (cipolla) ] [ 2drop f ] if ; |
|||
! Task |
|||
{ |
|||
{ 10 13 } |
|||
{ 56 101 } |
|||
{ 8218 10007 } |
|||
{ 8219 10007 } |
|||
{ 331575 1000003 } |
|||
{ 665165880 1000000007 } |
|||
{ 881398088036 1000000000039 } |
|||
${ |
|||
34035243914635549601583369544560650254325084643201 |
|||
10 50 ^ 151 + |
|||
} |
|||
} |
|||
[ |
|||
2dup cipolla |
|||
[ 2dup - [I Roots of ${3} are (${1} ${0}) mod ${2}I] ] |
|||
[ [I No solution for (${}, ${})I] ] if* nl |
|||
] assoc-each</lang> |
|||
{{out}} |
|||
<pre> |
|||
Roots of 10 are (6 7) mod 13 |
|||
Roots of 56 are (37 64) mod 101 |
|||
Roots of 8218 are (9872 135) mod 10007 |
|||
No solution for (8219, 10007) |
|||
Roots of 331575 are (855842 144161) mod 1000003 |
|||
Roots of 665165880 are (475131702 524868305) mod 1000000007 |
|||
Roots of 881398088036 are (791399408049 208600591990) mod 1000000000039 |
|||
Roots of 34035243914635549601583369544560650254325084643201 are (82563118828090362261378993957450213573687113690751 17436881171909637738621006042549786426312886309400) mod 100000000000000000000000000000000000000000000000151 |
|||
</pre> |
</pre> |
||