- iOS/Objective-C 元类和类别
- objective-c - -1001 错误,当 NSURLSession 通过 httpproxy 和/etc/hosts
- java - 使用网络类获取 url 地址
- ios - 推送通知中不播放声音
首先澄清一下:
我想要的是一个简单的算法,它最清楚地显示了 2^3.5 = 11.313708 的原理。除了基本的加法、减法、乘法或除法运算符外,它最好不要使用任何函数。
代码当然不一定要快,也不一定要短(尽管这会有所帮助)。别担心,它可以近似于给定的用户指定精度(这也应该是算法的一部分)。我希望会出现二进制印章/搜索类型的东西,因为这很容易理解。
到目前为止,我找到了 this ,但最佳答案在概念层面上远非简单易懂。
答案越多越好,因此我可以尝试理解解决问题的不同方法。
我对答案的语言偏好是 C#/C/C++/Java,或者我所关心的伪代码。
最佳答案
好吧,让我们只使用二进制搜索、加法和乘法来实现 pow(x, y)。
y
低于 1首先,解决这个问题:
pow(x, y) == pow(x*x, y/2)
pow(x, y) == 1/pow(x, -y)
这对于处理负指数和驱动很重要 y
下面1
,事情开始变得有趣。这将问题简化为查找 pow(x, y)
其中 0<y<1
.
sqrt
在这个答案中,我假设您知道如何执行 sqrt
.我知道sqrt(x) = x^(1/2)
, 但很容易实现它,只需使用二进制搜索来查找 y = sqrt(x)
使用 y*y=x
搜索功能,例如:
#define EPS 1e-8
double sqrt2(double x) {
double a = 0, b = x>1 ? x : 1;
while(abs(a-b) > EPS) {
double y = (a+b)/2;
if (y*y > x) b = y; else a = y;
}
return a;
}
基本原理是每个小于 1 的数字都可以近似为分数之和 1/2^x
:
0.875 = 1/2 + 1/4 + 1/8
0.333333... = 1/4 + 1/16 + 1/64 + 1/256 + ...
如果你找到这些分数,你实际上会发现:
x^0.875 = x^(1/2+1/4+1/8) = x^(1/2) * x^(1/4) * x^(1/8)
这最终导致
sqrt(x) * sqrt(sqrt(x)) * sqrt(sqrt(sqrt(x)))
#define EPS 1e-8
double pow2(double x, double y){
if (x < 0 and abs(round(y)-y) < EPS) {
return pow2(-x, y) * ((int)round(y)%2==1 ? -1 : 1);
} else if (y < 0) {
return 1/pow2(x, -y);
} else if(y > 1) {
return pow2(x * x, y / 2);
} else {
double fraction = 1;
double result = 1;
while(y > EPS) {
if (y >= fraction) {
y -= fraction;
result *= x;
}
fraction /= 2;
x = sqrt2(x);
}
return result;
}
}
关于c# - “Grokkable”算法,用于理解指数为 float 的求幂,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/29860973/
关闭。这个问题不满足Stack Overflow guidelines .它目前不接受答案。 想改善这个问题吗?更新问题,使其成为 on-topic对于堆栈溢出。 6年前关闭。 Improve thi
我有一个十进制的自然数 x 和一个三进制的自然数 n。如何使用最小乘法次数计算 x^n 的值? 我知道二进制系统的算法,我一直在寻找类比,但没有找到。 最佳答案 也许你需要这样的东西: functio
我怎样才能像在这个 python(使用 sage)代码中那样做: def elGamalDecrypt(c1, c2, p, x): return Mod(c2*c1^(-x),p) 使用标准
我尝试用 Kotlin 编写 Kleisli 求幂: fun kleisli(n: Int, f: (A) -> B): (A) -> B = if (n == 1) f else { it ->
考虑一下: const a = BigInt(2); const b = BigInt(2); const c = a ** b; Babel 会将其转换为: var a = BigInt(2); v
.NET 中内置的 Math.Pow() 函数将一个 double 基数提升为一个 double 指数并返回一个 双结果。 对整数执行相同操作的最佳方法是什么? 补充:似乎可以将 Math.Pow()
语句的含义是什么 // create arrays of 1M elements const int num_elements = 1 #include // this kernel compute
说, 基数 = 2 且 e = 20000.5671 如何在 Java 中执行上述示例的 (base power e)。 显然 Math.pow(base, e) 不是正确的方法,因为它打印的是“In
我是一名优秀的程序员,十分优秀!