Fermat numbers: Difference between revisions
Content added Content deleted
Drkameleon (talk | contribs) |
m (→{{header|Phix}}: added syntax colouring the hard way) |
||
| Line 1,394: | Line 1,394: | ||
=={{header|Phix}}== |
=={{header|Phix}}== |
||
{{libheader|Phix/mpfr}} |
{{libheader|Phix/mpfr}} |
||
<lang Phix>-- |
<!--<lang Phix>(phixonline)--> |
||
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span> |
|||
include mpfr.e |
|||
<span style="color: #000080;font-style:italic;">-- demo\rosetta\Fermat.exw</span> |
|||
<span style="color: #008080;">include</span> <span style="color: #004080;">mpfr</span><span style="color: #0000FF;">.</span><span style="color: #000000;">e</span> |
|||
procedure fermat(mpz res, integer n) |
|||
integer pn = power(2,n) |
|||
<span style="color: #008080;">procedure</span> <span style="color: #000000;">fermat</span><span style="color: #0000FF;">(</span><span style="color: #004080;">mpz</span> <span style="color: #000000;">res</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
mpz_ui_pow_ui(res,2,pn) |
|||
<span style="color: #004080;">integer</span> <span style="color: #000000;">pn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">power</span><span style="color: #0000FF;">(</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">n</span><span style="color: #0000FF;">)</span> |
|||
mpz_add_si(res,res,1) |
|||
<span style="color: #7060A8;">mpz_ui_pow_ui</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">2</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pn</span><span style="color: #0000FF;">)</span> |
|||
end procedure |
|||
<span style="color: #7060A8;">mpz_add_si</span><span style="color: #0000FF;">(</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">res</span><span style="color: #0000FF;">,</span><span style="color: #000000;">1</span><span style="color: #0000FF;">)</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span> |
|||
mpz fn = mpz_init() |
|||
for i=0 to 29 do -- (see note) |
|||
<span style="color: #004080;">mpz</span> <span style="color: #000000;">fn</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_init</span><span style="color: #0000FF;">()</span> |
|||
fermat(fn,i) |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">lim</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">18</span><span style="color: #0000FF;">:</span><span style="color: #000000;">29</span><span style="color: #0000FF;">),</span> <span style="color: #000080;font-style:italic;">-- (see note)</span> |
|||
if i<=20 then |
|||
<span style="color: #000000;">print_lim</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">16</span><span style="color: #0000FF;">:</span><span style="color: #000000;">20</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"F%d = %s\n",{i,shorten(mpz_get_str(fn))}) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">lim</span> <span style="color: #008080;">do</span> |
|||
else -- (since printing it takes too long...) |
|||
<span style="color: #000000;">fermat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
printf(1,"F%d has %,d digits\n",{i,mpz_sizeinbase(fn,10)}) |
|||
<span style="color: #008080;">if</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #000000;">print_lim</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"F%d = %s\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">mpz_get_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">))})</span> |
|||
end for |
|||
<span style="color: #008080;">else</span> <span style="color: #000080;font-style:italic;">-- (since printing it takes too long...)</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"F%d has %,d digits\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #7060A8;">mpz_sizeinbase</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">10</span><span style="color: #0000FF;">)})</span> |
|||
printf(1,"\n") |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
randstate state = gmp_randinit_mt() |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
for i=0 to 13 do |
|||
atom t = time() |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"\n"</span><span style="color: #0000FF;">)</span> |
|||
fermat(fn,i) |
|||
<span style="color: #008080;">constant</span> <span style="color: #000000;">flimit</span> <span style="color: #0000FF;">=</span> <span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #7060A8;">platform</span><span style="color: #0000FF;">()=</span><span style="color: #004600;">JS</span><span style="color: #0000FF;">?</span><span style="color: #000000;">11</span><span style="color: #0000FF;">:</span><span style="color: #000000;">13</span><span style="color: #0000FF;">)</span> |
|||
sequence f = mpz_prime_factors(fn, 200000) |
|||
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">0</span> <span style="color: #008080;">to</span> <span style="color: #000000;">flimit</span> <span style="color: #008080;">do</span> |
|||
t = time()-t |
|||
<span style="color: #004080;">atom</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()</span> |
|||
string fs = "", |
|||
<span style="color: #000000;">fermat</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">i</span><span style="color: #0000FF;">)</span> |
|||
ts = elapsed(t) |
|||
<span style="color: #004080;">sequence</span> <span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_prime_factors</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">200000</span><span style="color: #0000FF;">)</span> |
|||
if length(f[$])=1 then -- (as per docs) |
|||
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">time</span><span style="color: #0000FF;">()-</span><span style="color: #000000;">t</span> |
|||
mpz_set_str(fn,f[$][1]) |
|||
<span style="color: #004080;">string</span> <span style="color: #000000;">fs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">""</span><span style="color: #0000FF;">,</span> |
|||
if not mpz_probable_prime_p(fn, state) then |
|||
<span style="color: #000000;">ts</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">elapsed</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span> |
|||
if length(f)=1 then |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[$])=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> <span style="color: #000080;font-style:italic;">-- (as per docs)</span> |
|||
fs = " (not prime)" |
|||
<span style="color: #7060A8;">mpz_set_str</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">,</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[$][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
else |
|||
<span style="color: #008080;">if</span> <span style="color: #008080;">not</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
fs = " (last factor is not prime)" |
|||
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> <span style="color: #008080;">then</span> |
|||
end if |
|||
<span style="color: #000000;">fs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" (not prime)"</span> |
|||
end if |
|||
<span style="color: #008080;">else</span> |
|||
f[$][1] = shorten(f[$][1]) |
|||
<span style="color: #000000;">fs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" (last factor is not prime)"</span> |
|||
elsif length(f)=1 |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
and mpz_probable_prime_p(fn, state) then |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
fs = " (prime)" |
|||
<span style="color: #000000;">f</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)</span> |
|||
end if |
|||
<span style="color: #000000;">f</span><span style="color: #0000FF;">[$][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">shorten</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">[$][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">])</span> |
|||
fs = mpz_factorstring(f)&fs |
|||
<span style="color: #008080;">elsif</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">1</span> |
|||
printf(1,"Factors of F%d: %s [%s]\n",{i,fs,ts}) |
|||
<span style="color: #008080;">and</span> <span style="color: #7060A8;">mpz_prime</span><span style="color: #0000FF;">(</span><span style="color: #000000;">fn</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span> |
|||
| ⚫ | |||
<span style="color: #000000;">fs</span> <span style="color: #0000FF;">=</span> <span style="color: #008000;">" (prime)"</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span> |
|||
<span style="color: #000000;">fs</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">mpz_factorstring</span><span style="color: #0000FF;">(</span><span style="color: #000000;">f</span><span style="color: #0000FF;">)&</span><span style="color: #000000;">fs</span> |
|||
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"Factors of F%d: %s [%s]\n"</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">i</span><span style="color: #0000FF;">,</span><span style="color: #000000;">fs</span><span style="color: #0000FF;">,</span><span style="color: #000000;">ts</span><span style="color: #0000FF;">})</span> |
|||
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span> |
|||
| ⚫ | |||
{{out}} |
{{out}} |
||
Note that mpz_prime_factors(), a phix-specific extension to gmp, is designed to find small factors quickly and |
Note that mpz_prime_factors(), a phix-specific extension to gmp, is designed to find small factors quickly and |
||