草庐IT

c++ - 具有大整数的牛顿-拉夫森除法

coder 2024-02-02 原文

我正在编写一个 BigInt 类作为编程练习。它在 base-65536 中使用 2 的补码有符号整数的 vector (这样 32 位乘法就不会溢出。一旦我完全正常工作，我将增加基数)。

所有基本数学运算都经过编码，但有一个问题:使用我能够创建的基本算法，除法痛苦地很慢。 (它有点像商的每个数字的二进制除法......我不会发布它，除非有人想看到它......)

我想使用 Newton-Raphson 来找到(移位的)倒数，然后相乘(和移位)，而不是我的慢速算法。我想我已经掌握了基础知识:你给公式 (x1 = x0(2 - x0 * divisor)) 一个很好的初始猜测，然后经过一些迭代后，x 收敛到互惠的。这部分看起来很简单......但是在尝试将此公式应用于大整数时我遇到了一些问题:

问题 1:

因为我使用的是整数……好吧……我不能使用分数。这似乎导致 x 总是发散(x0 * 除数似乎必须 <2？)。我的直觉告诉我应该对方程式进行一些修改，使其可以计算整数(达到一定的准确性)，但我真的很难找出它是什么。 (我缺乏数学技能在这里打败了我......)我想我需要找到一些等价的方程式，而不是="">d 有 d*[base^somePower]?是否有像 (x1 = x0(2 - x0 * d)) 这样适用于整数的方程式？

问题 2:

当我使用牛顿公式求出一些数字的倒数时，结果最终只是比答案应该是的小一小部分……例如。当试图找到 4 的倒数(十进制)时:

x0 = 0.3
x1 = 0.24
x2 = 0.2496
x3 = 0.24999936
x4 = 0.2499999999983616
x5 = 0.24999999999999999999998926258176

如果我以 10 为基数表示数字，我会想要 25 的结果(并记住将乘积右移 2)。对于一些倒数，例如 1/3，您可以在知道自己有足够的准确性后简单地截断结果。但是如何从上面的结果中提取出正确的倒数呢？

抱歉，如果这一切都太模糊或者我要求太多。我浏览了 Wikipedia 和我可以在 Google 上找到的所有研究论文，但我觉得我正在用头撞墙。我感谢任何人能给我的帮助!

...

编辑:使算法正常工作，尽管它比我预期的要慢得多。与我的旧算法相比，我实际上失去了很多速度，即使是在有数千位数字的数字上......我仍然遗漏了一些东西。这不是乘法的问题，它非常快。 (我确实在使用 Karatsuba 的算法)。

对于任何感兴趣的人，这是我当前的 Newton-Raphson 算法迭代:

bigint operator/(const bigint& lhs, const bigint& rhs) {
    if (rhs == 0) throw overflow_error("Divide by zero exception");
    bigint dividend = lhs;
    bigint divisor = rhs;

    bool negative = 0;
    if (dividend < 0) {
        negative = !negative;
        dividend.invert();
    }
    if (divisor < 0) {
        negative = !negative;
        divisor.invert();
    }

    int k = dividend.numBits() + divisor.numBits();
    bigint pow2 = 1;
    pow2 <<= k + 1;

    bigint x = dividend - divisor;
    bigint lastx = 0;
    bigint lastlastx = 0;
    while (1) {
        x = (x * (pow2 - x * divisor)) >> k;
        if (x == lastx || x == lastlastx) break;
        lastlastx = lastx;
        lastx = x;
    }
    bigint quotient = dividend * x >> k;
    if (dividend - (quotient * divisor) >= divisor) quotient++;
    if (negative)quotient.invert();
    return quotient;
}

这是我的(非常丑陋的)旧算法，它更快:

bigint operator/(const bigint& lhs, const bigint & rhs) {
    if (rhs == 0) throw overflow_error("Divide by zero exception");
    bigint dividend = lhs;
    bigint divisor = rhs;

    bool negative = 0;
    if (dividend < 0) {
        negative = !negative;
        dividend.invert();
    }
    if (divisor < 0) {
        negative = !negative;
        divisor.invert();
    }

    bigint remainder = 0;
    bigint quotient = 0;
    while (dividend.value.size() > 0) {
        remainder.value.insert(remainder.value.begin(), dividend.value.at(dividend.value.size() - 1));
        remainder.value.push_back(0);
        remainder.unPad();
        dividend.value.pop_back();

        if (divisor > remainder) {
            quotient.value.push_back(0);
        } else {
            int count = 0;
            int i = MSB;
            bigint value = 0;
            while (i > 0) {
                bigint increase = divisor * i;
                bigint next = value + increase;
                if (next <= remainder) {
                    value = next;
                    count += i;
                }
                i >>= 1;
            }
            quotient.value.push_back(count);
            remainder -= value;
        }
    }

    for (int i = 0; i < quotient.value.size() / 2; i++) {
        int swap = quotient.value.at(i);
        quotient.value.at(i) = quotient.value.at((quotient.value.size() - 1) - i);
        quotient.value.at(quotient.value.size() - 1 - i) = swap;
    }

    if (negative)quotient.invert();
    quotient.unPad();
    return quotient;
}

最佳答案

首先，您可以在时间 O(n^2) 中实现除法并使用合理的常量，因此它不会比原始乘法慢(很多)。但是，如果您使用 Karatsuba -like 算法，甚至 FFT -based 乘法算法，那么你确实可以使用 Newton-Raphson 加速你的除法算法。

用于计算 x 倒数的 Newton-Raphson 迭代是 q[n+1]=q[n]*(2-q[n]*x).

假设我们要计算floor(2^k/B) 其中B 是一个正整数。 WLOG, B≤2^k;否则，商为 0。 x=B/2^k 的 Newton-Raphson 迭代产生 q[n+1]=q[n]*(2-q[n]*B/2^k) 。我们可以将其重新排列为

q[n+1]=q[n]*(2^(k+1)-q[n]*B) >> k

这种类型的每次迭代只需要整数乘法和位移。它是否收敛于 floor(2^k/B)？不必要。然而，在最坏的情况下，它最终会在 floor(2^k/B) 和 ceiling(2^k/B) 之间交替(证明它!)。因此，您可以使用一些不太聪明的测试来查看您是否属于这种情况，然后提取 floor(2^k/B)。 (这个“不太聪明的测试”应该比每次迭代中的乘法快很多；但是，优化这个东西会很好)。

事实上，计算 floor(2^k/B) 足以计算任何正整数 floor(A/B) A,B。取 k 使得 A*B≤2^k，并验证 floor(A/B)=A*ceiling(2^k/B) >> k.

最后，此方法的一个简单但重要的优化是在 Newton-Raphson 方法的早期迭代中截断乘法(即仅计算乘积的较高位)。之所以这样做，是因为早期迭代的结果与商数相去甚远，执行不准确也没有关系。 (改进这个论点并证明如果你适本地做这件事，你可以在 O(M(2n)) 时间内划分两个 ≤n 位整数，假设你可以在时间M(k)上乘以两个≤k位的整数，M(x)是一个递增的凸函数。

关于c++ - 具有大整数的牛顿-拉夫森除法，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/27801397/

拉夫ampcodequotientbigintc++algorithmintegerdivision

有关c++ - 具有大整数的牛顿-拉夫森除法的更多相关文章

  1. ruby - 具有身份验证的私有(private) Ruby Gem 服务器 - 2

    我想安装一个带有一些身份验证的私有(private)Rubygem服务器。我希望能够使用公共(public)Ubuntu服务器托管内部gem。我读到了http://docs.rubygems.org/read/chapter/18.但是那个没有身份验证-如我所见。然后我读到了https://github.com/cwninja/geminabox.但是当我使用基本身份验证(他们在他们的Wiki中有)时，它会提示从我的服务器获取源。所以。如何制作带有身份验证的私有(private)Rubygem服务器？这是不可能的吗？谢谢。编辑:Geminabox问题。我尝试“捆绑”以安装新的gem..

  2. ruby-on-rails - 如何优雅地重启 thin + nginx？ - 2

    我的瘦服务器配置了nginx，我的ROR应用程序正在它们上运行。在我发布代码更新时运行thinrestart会给我的应用程序带来一些停机时间。我试图弄清楚如何优雅地重启正在运行的Thin实例，但找不到好的解决方案。有没有人能做到这一点？ 最佳答案 #Restartjustthethinserverdescribedbythatconfigsudothin-C/etc/thin/mysite.ymlrestartNginx将继续运行并代理请求。如果您将Nginx设置为使用多个上游服务器，例如server{listen80;server

  3. ruby-on-rails - Rails 3.1 中具有相同形式的多个模型？ - 2

    我正在使用Rails3.1并在一个论坛上工作。我有一个名为Topic的模型，每个模型都有许多Post。当用户创建新主题时，他们也应该创建第一个Post。但是，我不确定如何以相同的形式执行此操作。这是我的代码:classTopic:destroyaccepts_nested_attributes_for:postsvalidates_presence_of:titleendclassPost...但这似乎不起作用。有什么想法吗？谢谢! 最佳答案 @Pablo的回答似乎有你需要的一切。但更具体地说...首先改变你View中的这一行对此#

  4. ruby - 使用 `+=` 和 `send` 方法 - 2

    如何将send与+=一起使用？a=20;a.send"+=",10undefinedmethod`+='for20:Fixnuma=20;a+=10=>30 最佳答案 恐怕你不能。+=不是方法，而是语法糖。参见http://www.ruby-doc.org/docs/ProgrammingRuby/html/tut_expressions.html它说Incommonwithmanyotherlanguages,Rubyhasasyntacticshortcut:a=a+2maybewrittenasa+=2.你能做的最好的事情是:

  5. ruby - 如何计算 Liquid 中的变量 +1 - 2

    我对如何计算通过{%assignvar=0%}赋值的变量加一完全感到困惑。这应该是最简单的任务。到目前为止，这是我尝试过的:{%assignamount=0%}{%forvariantinproduct.variants%}{%assignamount=amount+1%}{%endfor%}Amount:{{amount}}结果总是0。也许我忽略了一些明显的东西。也许有更好的方法。我想要存档的只是获取运行的迭代次数。 最佳答案 因为{{incrementamount}}将输出您的变量值并且不会影响{%assign%}定义的变量，我

  6. ruby - 在 Ruby 中将整数格式化为固定长度的字符串 - 2

    有没有一种简单的方法可以将给定的整数格式化为具有固定长度和前导零的字符串？#convertnumberstostringsoffixedlength3[1,12,123,1234].map{|e|???}=>["001","012","123","234"]我找到了解决方案，但也许还有更聪明的方法。format('%03d',e)[-3..-1] 最佳答案 如何使用%1000而不是进行字符串操作来获取最后三位数字？[1,12,123,1234].map{|e|format('%03d',e%1000)}更新:根据theTinMan的

  7. ruby - 具有两个参数的 block - 2

    我从用户Hirolau那里找到了这段代码:defsum_to_n?(a,n)a.combination(2).find{|x,y|x+y==n}enda=[1,2,3,4,5]sum_to_n?(a,9)#=>[4,5]sum_to_n?(a,11)#=>nil我如何知道何时可以将两个参数发送到预定义方法(如find)？我不清楚，因为有时它不起作用。这是重新定义的东西吗？ 最佳答案 如果您查看Enumerable#find的文档，您会发现它只接受一个block参数。您可以将它发送两次的原因是因为Ruby可以方便地让您根据它的“并行赋

  8. ruby-on-rails - 在 RSpec 中，如何以任意顺序期望具有不同参数的多条消息？ - 2

    RSpec似乎按顺序匹配方法接收的消息。我不确定如何使以下代码工作:allow(a).toreceive(:f)expect(a).toreceive(:f).with(2)a.f(1)a.f(2)a.f(3)我问的原因是a.f的一些调用是由我的代码的上层控制的，所以我不能对这些方法调用添加期望。 最佳答案 RSpecspy是测试这种情况的一种方式。要监视一个方法，用allowstub，除了方法名称之外没有任何约束，调用该方法，然后expect确切的方法调用。例如:allow(a).toreceive(:f)a.f(2)a.f(1)

  9. ruby - 如何搜索、递增和替换 Ruby 字符串中的整数子字符串？ - 2

    我有很多这样的文档:foo_1foo_2foo_3bar_1foo_4...我想通过获取foo_[X]的所有实例并将它们中的每一个替换为foo_[X+1]来转换它们。在这个例子中:foo_2foo_3foo_4bar_1foo_5...我可以用gsub和一个block来做到这一点吗？如果不是，最干净的方法是什么？我真的在寻找一个优雅的解决方案，因为我总是可以暴力破解它，但我觉得有一些正则表达式技巧值得学习。 最佳答案 我(完全)不懂Ruby，但类似这样的东西应该可以工作:"foo_1foo_2".gsub(/(foo_)(\d+)/

  10. ruby-on-rails - 具有同名的模块和类 - 2

    我有一个模块stat存在于目录结构中:lib/stat_creator/stat/在lib/stat_creator/stat.rb中，我在lib/stat_creator/stat/目录中有我需要的文件，以及:moduleStatCreatormoduleStatendend当我使用该模块时，我将这些类称为StatCreator::Stat::Foo.new现在我想要一个存在于应用程序中的根Stat类。我在app/models中制作了我的Stat类，并在routes.rb中进行了设置。但是，如果我转到Rails控制台并尝试在应用程序/模型中使用Stat类，例如:Stat.by_use

随机推荐