整数除法算法 [英] Integer division algorithm

问题描述

我正在考虑一个大数除法的算法：用bigint D除以余数bigint C，其中我们知道基数b中C的表示，D的形式为b ^ k-1。这可能是最容易显示它的一个例子。让我们尝试将C = 21979182173除以D = 999。

I was thinking about an algorithm in division of large numbers: dividing with remainder bigint C by bigint D, where we know the representation of C in base b, and D is of form b^k-1. It's probably the easiest to show it on an example. Let's try dividing C=21979182173 by D=999.

• 我们将数字写成三位数：21 979 182 173


• 从左边开始，我们取连续集合的总和（模数999）：21 001 183 356


• 超过999：22 001 183 356

确实，21979182173/999 = 22001183和其余的356。

Indeed, 21979182173/999=22001183 and remainder 356.

我已经计算了复杂性，如果我没有错误，算法应该在O（n）中工作，n是基本b表示中的C的数字数。我也做了一个非常粗糙和未优化版本的算法（只适用于b = 10）在C + +，测试它对GMP的通用整数除法算法，它真的看起来好于GMP。我找不到像这样实现的任何地方我实现的任何地方，所以我不得不诉诸测试它对一般部门。

I've calculated the complexity and, if I'm not mistaken, the algorithm should work in O(n), n being the number of digits of C in base b representation. I've also done a very crude and unoptimized version of the algorithm (only for b=10) in C++, tested it against GMP's general integer division algorithm and it really does seem to fare better than GMP. I couldn't find anything like this implemented anywhere I looked, so I had to resort to testing it against general division.

我发现了几篇文章，讨论什么似乎非常类似的事情，但没有一个专注于实际的实现，特别是在不同于2的基数。我想这是因为数字内部存储，虽然所提到的算法似乎有用的，比如说，b = 10，帐户。我也尝试联系其他人，但是，再一次，没有效果。

I found several articles which discuss what seem to be quite similar matters, but none of them concentrate on actual implementations, especially in bases different than 2. I suppose that's because of the way numbers are internally stored, although the mentioned algorithm seems useful for, say, b=10, even taking that into account. I also tried contacting some other people, but, again, to no avail.

因此，我的问题是：有一篇文章或一本书或东西，上述算法被描述，可能讨论的实现？如果没有，对我来说，尝试和实现和测试这样的算法，比如说C / C ++或者这种算法有点固有的坏？

Thus, my question would be: is there an article or a book or something where the aforementioned algorithm is described, possibly discussing the implementations? If not, would it make sense for me to try and implement and test such an algorithm in, say, C/C++ or is this algorithm somehow inherently bad?

此外，我不是一个程序员，虽然我在编程时相当不错，但我承认没有太多的计算机内部知识。因此，原谅我的无知 - 这很可能在这篇文章中有一个或多个非常愚蠢的东西。非常抱歉。

Also, I'm not a programmer and while I'm reasonably OK at programming, I admittedly don't have much knowledge of computer "internals". Thus, pardon my ignorance - it's highly possible there are one or more very stupid things in this post. Sorry once again.

非常感谢！

em>进一步澄清在评论/答案中提出的观点：

Further clarification of points raised in the comments/answers:

感谢大家 - 因为我不想评论所有伟大的答案，

Thanks, everyone - as I didn't want to comment on all the great answers and advice with the same thing, I'd just like to address one point a lot of you touched on.

我完全知道在基地工作2 ^ n是，但是，一般来说，显然是最有效的做事方式。几乎所有bigint库使用2 ^ 32或任何。然而，如果（和，我强调，这将是有用的只有这个特定的算法！）我们实现bigints作为一个数组在基数b？当然，我们要求b在这里是合理的：b = 10，最自然的情况，似乎足够合理。我知道考虑到内存和时间，考虑到内部存储的数字，但是我已经能够，如果我的（基本的，可能有点错误的）测试是正确的，产生的结果比GMP的一般划分更快或更低的效率，这将有助于实现这样的算法。

I am fully aware that working in bases 2^n is, generally speaking, clearly the most efficient way of doing things. Pretty much all bigint libraries use 2^32 or whatever. However, what if (and, I emphasize, it would be useful only for this particular algorithm!) we implement bigints as an array of digits in base b? Of course, we require b here to be "reasonable": b=10, the most natural case, seems reasonable enough. I know it's more or less inefficient both considering memory and time, taking into account how numbers are internally stored, but I have been able to, if my (basic and possibly somehow flawed) tests are correct, produce results faster than GMP's general division, which would give sense to implementing such an algorithm.

Ninefingers注意我必须使用在这种情况下昂贵的模运算。我希望不会：我可以看到，如果老+新的交叉，说，999，只是通过查看旧+新+ 1的数字的数量。如果它有4位数，我们就完成了。由于旧的< 999和新的< = 999，我们知道如果old + new + 1有4位数字（它不能有更多），那么，（old + new）％999等于删除old + new + 1），我假设我们可以做到便宜。

Ninefingers notices I'd have to use in that case an expensive modulo operation. I hope not: I can see if old+new crossed, say, 999, just by looking at the number of digits of old+new+1. If it has 4 digits, we're done. Even more, since old<999 and new<=999, we know that if old+new+1 has 4 digits (it can't have more), then, (old+new)%999 equals deleting the leftmost digit of (old+new+1), which I presume we can do cheaply.

当然，我不是争论这个算法的明显限制，改进 - 它只能与某一类数字相除，我们必须先验知道基底b中的股利表示。然而，对于b = 10，例如，后者似乎是自然的。

Of course, I'm not disputing obvious limitations of this algorithm nor I claim it can't be improved - it can only divide with a certain class of numbers and we have to a priori know the representation of dividend in base b. However, for b=10, for instance, the latter seems natural.

现在，我们已经实现了bignums，如上所述。在基底b中说C =（a_1a_2 ... a_n），并且D = b ^ k-1。算法（可能更加优化）会像这样。

Now, say we have implemented bignums as I outlined above. Say C=(a_1a_2...a_n) in base b and D=b^k-1. The algorithm (which could be probably much more optimized) would go like this. I hope there aren't many typos.

• 如果k> n，我们显然已经完成了


• 在C 开头添加一个零（即a_0 = 0）（只是为了防止我们尝试用99除以9999）


• l = n％k （mod为常规整数 - 不应太贵）


• old =（a_0 ... a_l） （i = 1 + 1; i 的第一组数字（可能具有小于k个数字）
（我们将有大约（n / k）次迭代）



• new =（a_i ... a_（i + k-1） li>
  
• new = new + old （这是bigint的加法，因此O（k））
em>

• 如果aux有超过k个数字
  
  
  
  • 删除aux的第一个数字
  
  
  • old = old + 1 （再次添加bigint）
  
  
  • （a_（ik）... a_（i-1））= old 如果i = 1 + 1，（a _ 0 ... a _ l）= old）
  new = aux
  
  • if k>n, we're obviously done
  • add a zero (i.e. a_0=0) at the beginning of C (just in case we try to divide, say, 9999 with 99)
  • l=n%k (mod for "regular" integers - shouldn't be too expensive)
  • old=(a_0...a_l) (the first set of digits, possibly with less than k digits)
  • for (i=l+1; i < n; i=i+k) (We will have floor(n/k) or so iterations)
    • new=(a_i...a_(i+k-1))
    • new=new+old (this is bigint addition, thus O(k))
    • aux=new+1 (again, bigint addition - O(k) - which I'm not happy about)
    • if aux has more than k digits
      • delete first digit of aux
      • old=old+1 (bigint addition once again)
      • fill old with zeroes at the beginning so it has as much digits as it should
      • (a_(i-k)...a_(i-1))=old (if i=l+1, (a _ 0...a _ l)=old)
      • new=aux

      与我 - 如我所说，这似乎是一个有趣的特殊情况算法尝试实施，测试和讨论，如果没有人看到任何致命的缺陷。如果到目前为止还没有广泛讨论，甚至更好。请让我知道你的想法。

      There, thanks for discussing this with me - as I said, this does seem to me to be an interesting "special case" algorithm to try to implement, test and discuss, if nobody sees any fatal flaws in it. If it's something not widely discussed so far, even better. Please, let me know what you think. Sorry about the long post.

      此外，还有几个个人意见：

      Also, just a few more personal comments:

      @ Ninefingers：有一些（非常基本的）知识如何GMP工作，它做了什么和一般bigint分割算法，所以我能够理解你的很多参数。我也知道GMP是高度优化的，并以某种方式为不同的平台自定义，所以我一定不是试图击败一般 - 似乎是一个有效的攻击坦克用一个尖的棒。然而，这不是这个算法的想法 - 它在非常特殊的情况下工作（GMP似乎没有覆盖）。在一个不相关的注释，你确定一般划分是在O（n）？我所见过的最多的是M（n）。 （如果我理解正确，在实践中（Schönhage-Strassen等）没有达到O（n）。Fürer的算法，仍然没有达到O（n），如果我是正确的，几乎纯粹理论上。）

      @Ninefingers: I actually have some (very basic!) knowledge of how GMP works, what it does and of general bigint division algorithms, so I was able to understand much of your argument. I'm also aware GMP is highly optimized and in a way customizes itself for different platforms, so I'm certainly not trying to "beat it" in general - that seems as much fruitful as attacking a tank with a pointed stick. However, that's not the idea of this algorithm - it works in very special cases (which GMP does not appear to cover). On an unrelated note, are you sure general divisions are done in O(n)? The most I've seen done is M(n). (And that can, if I understand correctly, in practice (Schönhage–Strassen etc.) not reach O(n). Fürer's algorithm, which still doesn't reach O(n), is, if I'm correct, almost purely theoretical.)

      @Avi Berger：这似乎与转出九完全一样，虽然这个想法是相似的。

      @Avi Berger: This doesn't actually seem to be exactly the same as "casting out nines", although the idea is similar. However, the aforementioned algorithm should work all the time, if I'm not mistaken.

      推荐答案

      您的算法是一个变体base 10算法称为铸出九。你的例子是使用base 1000和推出999的（一个比基地）。这以前在小学教给做一个快速检查手计算的方法。我有一个高中数学老师，他害怕得知它没有被教学，并填补了我们。

      Your algorithm is a variation of a base 10 algorithm known as "casting out nines". Your example is using base 1000 and "casting out" 999's (one less than the base). This used to be taught in elementary school as way to do a quick check on hand calculations. I had a high school math teacher who was horrified to learn that it wasn't being taught anymore and filled us in on it.

      铸造999基础1000韩元t作为通用分割算法。它将生成与实际商和余数（而不是实际值）相等的模数999的值。你的算法有点不同，我没有检查它是否工作，但它是基于有效地使用基地1000和除数为1小于基数。如果您想尝试将其除以47，您必须先转换为基本48号码系统。

      Casting out 999's in base 1000 won't work as a general division algorithm. It will generate values that are congruent modulo 999 to the actual quotient and remainder - not the actual values. Your algorithm is a bit different and I haven't checked if it works, but it is based on effectively using base 1000 and the divisor being 1 less than the base. If you wanted to try it for dividing by 47, you would have to convert to a base 48 number system first.

      Google投放九以获取更多信息。

      Google "casting out nines" for more information.

      编辑：我最初读你的文章有点太快了，你知道这是一个工作算法。因为@Ninefingers和@Karl Bielefeldt在他们的评论中比我更清楚地说明了你的表现估计中没有包括的是转换成适合于特定除数的基数。

      I originally read your post a bit too quickly, and you do know of this as a working algorithm. As @Ninefingers and @Karl Bielefeldt have stated more clearly than me in their comments, what you aren't including in your performance estimate is the conversion into a base appropriate for the particular divisor at hand.

      这篇关于整数除法算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！