LMMP 4.3.0
Lamina High-Precision Arithmetic Library
载入中...
搜索中...
未找到
sqrt_1.c
浏览该文件的文档.
1/**
2 * Copyright (C) 2026 HJimmyK (Jericho Knox)
3 *
4 * This file is part of LMMP.
5 *
6 * LMMP is free software: you can redistribute it and/or modify it
7 * under the terms of the GNU Lesser General Public License as
8 * published by the Free Software Foundation; either version 3 of
9 * the License, or (at your option) any later version.
10 *
11 * This library is distributed in the hope that it will be useful,
12 * but WITHOUT ANY WARRANTY; without even the implied warranty of
13 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
14 * GNU Lesser General Public License for more details.
15 *
16 * You should have received a copy of the GNU Lesser General Public
17 * License along with this library. If not, see
18 * <https://www.gnu.org/licenses/>.
19 *
20 * SPDX-License-Identifier: LGPL-3.0-or-later
21 */
22
23#include <math.h>
24
25#include "impl/inlines.h"
26#include "impl/longlong.h"
27#include "mparam.h"
28#include "lmmp/numth.h"
29
30
32 ulong is;
33
34 is = (ulong)sqrt((double)a);
35
36 is -= (is * is > a);
37 if (is == (1ULL << 32))
38 is--;
39 return is;
40}
41
45 *dstr = x - s * s;
46 return s;
47}
48
50 lmmp_param_assert(numa[1] >= LIMB_B_4);
51 mp_limb_t rl, s, q, al, u;
52 mp_slimb_t rh;
53
54 s = lmmp_sqrt_1_(&rl, numa[1]);
55 al = numa[0];
56
57 //(r:alh)/2
58 rl = rl << 31 | al >> 33;
59 q = rl / s;
60 q -= q >> 32;
61
62 u = rl - s * q;
63 s = s << 32 | q;
64 rh = u >> 31;
65 rl = (u << 33) | (al & (((mp_limb_t)1 << 33) - 1));
66
67 q *= q;
68 rh -= rl < q;
69 rl -= q;
70 if (rh < 0) {
71 rl += s;
72 rh += rl < s;
73 --s;
74 rl += s;
75 rh += rl < s;
76 }
77
78 dstr[0] = rl;
79 dstr[1] = rh;
80 return s;
81}
82
83/*
84 以 4 limb 为例,x = x3*B^3 + x2*B^2 + x1*B + x0(x3 >= B/4):
85
86 (s', rh) = sqrtrem(x3*B + x2) 2 limb 根,rh <= 2s'
87 N = rh*B + x1
88 (Q2, u) = divrem(N, s') 顶 limb 先归约至 s' 以下
89 s_low = Q2 >> 1 s = s'*B + s_low
90 r = (N mod 2s')*B + x0 - s_low^2
91
92 r < 0 时 s -= 1、r += 2s+1 一步修正(Karatsuba 平方根保证 Q2 至多
93 高估 2,修正至多一步);修正后 r = x - s^2 <= 2s 恒成立。
94 3 limb 输入采用 beta = 2^32 的非均衡分割(s = s'*2^32 + q,商 33
95 bit),其余同理。
96*/
97
98void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa) {
99 lmmp_param_assert(numa != NULL && dsts != NULL);
100 lmmp_param_assert(numa[2] >= LIMB_B_4);
101 mp_limb_t a0 = numa[0];
102 mp_limb_t rh[2], n1, n0, q, u, uc, s1, s0, r1, r0, p[2], neg;
103
104 // s' = sqrt([a2,a1]) >= 2^63,rh = [a2,a1] - s'^2 <= 2s'
105 mp_limb_t sh = lmmp_sqrt_2_(rh, numa + 1);
106
107 // N = rh*2^32 + (a0>>32) < 2^34*s',N/s' < 2^34,n1 = N>>64 < s'
108 n1 = (rh[1] << 32) | (rh[0] >> 32);
109 n0 = (rh[0] << 32) | (a0 >> 32);
110 mp_limb_t qh = _udiv128by64to64_(n1, n0, sh, &u);
111 // q = N div 2s',(uc,u) = N mod 2s'
112 q = qh >> 1;
113 _add_ssaaaa(uc, u, 0, u, 0, sh & (-(qh & 1)));
114
115 // s = s'*2^32 + q
116 _add_ssaaaa(s1, s0, sh >> 32, sh << 32, 0, q);
117
118 // r = u*2^32 + (a0 & M32) - q^2,|r| < 2^98(双 limb 有符号)
119 lmmp_mullh_(q, q, p);
120 _sub_ddmmss(r1, r0, (uc << 32) | (u >> 32), (u << 32) | (a0 & (((mp_limb_t)1 << 32) - 1)),
121 p[1], p[0]);
122
123 // r < 0(概率约 1/4):s -= 1,r += 2s + 1,(s0<<1)|1 = 2*s0+1 无进位
124 neg = -(r1 >> (LIMB_BITS - 1));
125 _sub_ddmmss(s1, s0, s1, s0, 0, neg & 1);
126 _add_ssaaaa(r1, r0, r1, r0, neg & ((s1 << 1) | (s0 >> (LIMB_BITS - 1))),
127 neg & ((s0 << 1) | 1));
128
129 dsts[0] = s0;
130 dsts[1] = s1;
131 if (dstr != NULL) {
132 dstr[0] = r0;
133 dstr[1] = r1;
134 dstr[2] = 0;
135 }
136}
137
138void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa) {
139 lmmp_param_assert(numa != NULL && dsts != NULL);
140 lmmp_param_assert(numa[3] >= LIMB_B_4);
141 mp_limb_t x0 = numa[0], x1 = numa[1];
142 mp_limb_t rh[2], qh, ql, u, uc, t, s1, s0, r2, r1, r0, p[2], b, neg;
143
144 // s' = sqrt([x3,x2]) >= 2^63,rh = [x3,x2] - s'^2 <= 2s'
145 mp_limb_t sh = lmmp_sqrt_2_(rh, numa + 2);
146
147 // N = rh*B + x1 除以 s':先把顶 limb 归约到 s' 以下(至多两次),商计入学 qh
148 qh = rh[1];
149 rh[0] -= sh & (-(mp_limb_t)(rh[1] != 0));
150 t = (rh[0] >= sh);
151 rh[0] -= sh & (-(mp_limb_t)t);
152 qh += t;
153 ql = _udiv128by64to64_(rh[0], x1, sh, &u);
154
155 // N div s' = qh*B + ql = 2*s_low + (ql&1),N mod 2s' = u + (ql&1)*s'
156 s0 = (ql >> 1) | (qh << (LIMB_BITS - 1));
157 qh >>= 1;
158 _add_ssaaaa(uc, u, 0, u, 0, sh & (-(ql & 1)));
159
160 // r = (uc,u)*B + x0 - s_low^2,s_low = qh*B + s0 <= B(qh=1 时 s0=0)
161 lmmp_mullh_(s0, s0, p);
162 _sub_ddmmss(r1, r0, u, x0, p[1], p[0]);
163 b = (u < p[1]) | ((u == p[1]) & (x0 < p[0]));
164 r2 = uc - qh - b;
165
166 // s = s'*B + s_low;sh = B-1 且 s_low = B 时 s1 回绕为 0,r < 0 修正时解开
167 s1 = sh + qh;
168 neg = -(r2 >> (LIMB_BITS - 1));
169 _sub_ddmmss(s1, s0, s1, s0, 0, neg & 1);
170 // r += 2s + 1:低位 (s0<<1)|1 = 2*s0+1 无进位,进位链并入 r2
171 {
172 mp_limb_t al = neg & ((s0 << 1) | 1);
173 mp_limb_t ah = neg & ((s1 << 1) | (s0 >> (LIMB_BITS - 1)));
174 __uint128_t tc;
175
176 tc = (__uint128_t)r0 + al;
177 r0 = (mp_limb_t)tc;
178 tc = (__uint128_t)r1 + ah + (mp_limb_t)(tc >> 64);
179 r1 = (mp_limb_t)tc;
180 r2 += (neg & (s1 >> (LIMB_BITS - 1))) + (mp_limb_t)(tc >> 64);
181 }
182
183 dsts[0] = s0;
184 dsts[1] = s1;
185 if (dstr != NULL) {
186 dstr[0] = r0;
187 dstr[1] = r1;
188 dstr[2] = r2;
189 }
190}
#define lmmp_mullh_
#define LIMB_B_4
mp_limb_t * mp_ptr
定义 lmmp.h:96
int64_t mp_slimb_t
定义 lmmp.h:94
const mp_limb_t * mp_srcptr
定义 lmmp.h:97
uint64_t mp_limb_t
定义 lmmp.h:92
#define LIMB_BITS
定义 lmmp.h:102
#define lmmp_param_assert(x)
定义 lmmp.h:509
#define _sub_ddmmss(sh, sl, ah, al, bh, bl)
static uint64_t _udiv128by64to64_(uint64_t numhi, uint64_t numlo, uint64_t den, uint64_t *r)
#define _add_ssaaaa(sh, sl, ah, al, bh, bl)
#define a0
#define r2
#define r1
#define r0
#define t
#define s
void lmmp_sqrt_3_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,3]))
mp_limb_t lmmp_sqrt_1_(mp_ptr dstr, mp_limb_t x)
计算算术平方根 floor(sqrt(x))
ulong lmmp_sqrt_ulong_(ulong a)
计算算术平方根 floor(sqrt(a))
mp_limb_t lmmp_sqrt_2_(mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,2]))
void lmmp_sqrt_4_(mp_ptr dsts, mp_ptr dstr, mp_srcptr numa)
计算算术平方根 floor(sqrt([numa,4]))
uint64_t ulong
定义 numth.h:39