P-Adic square roots: Difference between revisions
Content added Content deleted
(→{{header|Wren}}: Updated in line with changes to FB example.) |
(max. p-adic precision with standard data types) |
||
Line 47: | Line 47: | ||
const emx = |
const emx = 48 |
||
'exponent maximum |
'exponent maximum |
||
const amx = |
const amx = 700000 |
||
'tentative argument maximum |
'tentative argument maximum |
||
'------------------------------------------------ |
'------------------------------------------------ |
||
const Mxd = cdbl(2)^53 - 1 |
|||
'max. float64 integer |
|||
const Pmax = 32749 |
const Pmax = 32749 |
||
'max. prime < 2^15 |
'max. prime < 2^15 |
||
Line 93: | Line 96: | ||
function padic.sqrt (byref g as ratio, byval sw as integer) as integer |
function padic.sqrt (byref g as ratio, byval sw as integer) as integer |
||
dim as longint a = g.a, b = g.b |
dim as longint a = g.a, b = g.b |
||
dim as longint |
dim as longint q, x, pk |
||
dim as long f1, r, s, t |
dim as long f1, r, s, t |
||
dim i as integer |
dim i as integer, f as double |
||
sqrt = 0 |
sqrt = 0 |
||
Line 152: | Line 155: | ||
'find root for small p |
'find root for small p |
||
for r = 1 to p1 |
for r = 1 to p1 |
||
q = b * r * r - a |
|||
if |
if q mod p = 0 then exit for |
||
next r |
next r |
||
Line 181: | Line 184: | ||
'evaluate f(x) |
'evaluate f(x) |
||
#macro evalf(x) |
#macro evalf(x) |
||
f = b * x * x |
f = b * x * cdbl(x / pk) |
||
f -= cdbl(a / pk) |
|||
'overflow |
'overflow |
||
if f |
if f > Mxd then exit for |
||
q = clngint(f) |
|||
#endmacro |
#endmacro |
||
Line 229: | Line 233: | ||
function padic.crat (byval sw as integer) as ratio |
function padic.crat (byval sw as integer) as ratio |
||
dim as integer i, j, t = min(v, 0) |
dim as integer i, j, t = min(v, 0) |
||
dim |
dim as longint s, pk, pm |
||
dim as long x, y |
dim as long q, x, y |
||
dim as |
dim as double f, h |
||
dim r as ratio |
|||
'weighted digit sum |
'weighted digit sum |
||
s = 0: pk = 1 |
s = 0: pk = 1 |
||
for i = t to k - 1 + v |
for i = t to k - 1 + v |
||
pm = pk: pk *= p |
|||
if pk \ |
if pk \ pm - p then |
||
'overflow |
'overflow |
||
pk = |
pk = pm: exit for |
||
end if |
end if |
||
s += d(i) * |
s += d(i) * pm '(mod pk) |
||
next i |
next i |
||
Line 249: | Line 254: | ||
dim as longint m(1) = {pk, s} |
dim as longint m(1) = {pk, s} |
||
dim as longint n(1) = {0, 1} |
dim as longint n(1) = {0, 1} |
||
⚫ | |||
h = cdbl(s) * s + 1 |
|||
i = 0: j = 1 |
i = 0: j = 1 |
||
⚫ | |||
'Lagrange's algorithm |
'Lagrange's algorithm |
||
do |
do |
||
f = m(i) * |
f = m(i) * (m(j) / h) |
||
f += n(i) * |
f += n(i) * (n(j) / h) |
||
'Euclidean step |
'Euclidean step |
||
Line 262: | Line 268: | ||
n(i) -= q * n(j) |
n(i) -= q * n(j) |
||
f = h |
|||
h = cdbl(m(i)) * m(i) |
|||
h += cdbl(n(i)) * n(i) |
|||
'compare norms |
'compare norms |
||
if |
if h < f then |
||
'interchange vectors |
'interchange vectors |
||
swap i, j |
swap i, j |
||
Line 375: | Line 382: | ||
data 10496,497, 2,19 |
data 10496,497, 2,19 |
||
data |
data -577215,664901, 3,23 |
||
data |
data 15403,26685, 3,18 |
||
data -1,1, 5,8 |
data -1,1, 5,8 |
||
Line 383: | Line 390: | ||
data 2,1, 7,8 |
data 2,1, 7,8 |
||
data |
data 11696,621467, 7,11 |
||
data |
data -27764,11521, 7,11 |
||
data |
data -27584,12953, 7,11 |
||
data |
data -166420,135131, 11,11 |
||
data |
data 14142,135623, 5,15 |
||
data -255,256, 257,3 |
data -255,256, 257,3 |
||
Line 423: | Line 430: | ||
loop |
loop |
||
end |
|||
system |
|||
</lang> |
</lang> |
||
{{out|Examples}} |
{{out|Examples}} |
||
<pre> |
<pre> |
||
Line 478: | Line 486: | ||
-577215/664901 + O(3^23) |
|||
lift: |
lift: 44765673211 mod 3^23 |
||
sqrt +/- |
sqrt +/- |
||
... |
... 1 0 2 1 1 1 2 2 1 0 1 1 1 2 1 1 0 1 0 2 0 1 0 |
||
... |
... 1 2 0 1 1 1 0 0 1 2 1 1 1 0 1 1 2 1 2 0 2 2 0 |
||
sqrt^2 |
sqrt^2 |
||
0 1 2 1 1 0 0 2 1 1 0 0 1 1 0 2 0 1 1 0 1 0 0 |
|||
-577215/664901 |
|||
3141/5926 |
|||
15403/26685 + O(3^18) |
|||
lift: |
lift: 238961782 mod 3^18 |
||
sqrt +/- |
sqrt +/- |
||
... |
... 1 2 1 1 2 2 1 2 2 1 1 1 2 2 1 1 0. 1 |
||
... |
... 1 0 1 1 0 0 1 0 0 1 1 1 0 0 1 1 2. 2 |
||
sqrt^2 |
sqrt^2 |
||
2 2 |
1 2 1 2 0 1 2 2 0 1 1 0 1 2 2 2. 0 1 |
||
15403/26685 |
|||
2718/281 |
|||
Line 538: | Line 546: | ||
11696/621467 + O(7^11) |
|||
lift: |
lift: 967215488 mod 7^11 |
||
sqrt +/- |
sqrt +/- |
||
... 6 5 3 1 2 4 1 4. 1 |
... 3 2 6 5 3 1 2 4 1 4. 1 |
||
... 0 1 3 5 4 2 5 2. 6 |
... 3 4 0 1 3 5 4 2 5 2. 6 |
||
sqrt^2 |
sqrt^2 |
||
1 1 3 3 4 4 5. 1 1 |
3 3 1 1 3 3 4 4 5. 1 1 |
||
11696/621467 |
|||
-2645/28518 |
|||
-27764/11521 + O(7^11) |
|||
lift: |
lift: 453209984 mod 7^11 |
||
sqrt +/- |
sqrt +/- |
||
... |
... 1 4 1 4 2 1 3 5 6 2 3 |
||
... |
... 5 2 5 2 4 5 3 1 0 4 4 |
||
sqrt^2 |
sqrt^2 |
||
5 1 0 2 5 5 5 3 6 6 2 |
|||
-27764/11521 |
|||
3029/4821 |
|||
-27584/12953 + O(7^11) |
|||
lift: |
lift: 1239987302 mod 7^11 |
||
sqrt +/- |
sqrt +/- |
||
... 0 4 5 0 1 2 2 1 |
... 4 2 5 0 4 5 0 1 2 2 1 |
||
... 6 2 1 6 5 4 4 6 |
... 2 4 1 6 2 1 6 5 4 4 6 |
||
sqrt^2 |
sqrt^2 |
||
5 3 1 2 4 1 4 1 |
3 2 6 5 3 1 2 4 1 4 1 |
||
-27584/12953 |
|||
379/449 |
|||
-166420/135131 + O(11^11) |
|||
lift: |
lift: 34219617965 mod 11^11 |
||
sqrt +/- |
sqrt +/- |
||
... |
... 1 3 5 7 0 0 9 10 5 0 5 |
||
... |
... 9 7 5 3 10 10 1 0 5 10 6 |
||
sqrt^2 |
sqrt^2 |
||
1 4 1 4 2 1 3 |
1 4 1 4 2 1 3 5 6 2 3 |
||
-166420/135131 |
|||
717/8 |
|||
14142/135623 + O(5^15) |
|||
lift: |
lift: 236397452 mod 5^15 |
||
sqrt +/- |
sqrt +/- |
||
... |
... 0 0 0 4 4 1 0 0 4 2 0 4 3 0 2 |
||
... |
... 4 4 4 0 0 3 4 4 0 2 4 0 1 4 3 |
||
sqrt^2 |
sqrt^2 |
||
4 2 1 3 3 4 3 4 3 4 2 3 2 0 4 |
|||
14142/135623 |
|||
1414/213 |
|||