如何將一個大整數除以另一個大整數？

Question

我一直在研究這最後幾天，我一直無法拿出一個答案。如果除數只有一個單詞，我想出了一種算法。但是，如果除數是多個詞，那麼我會得到一些奇怪的答案。我知道這個問題在這裏已經被問了幾次，但是除了使用教科書方法或者去拿一本關於這個主題的書之外，還沒有確定的答案。除了部門之外，我已經能夠讓我的大整數庫中的每個函數都能工作。似乎有些人認爲大整數劃分是一個NP難題，而且我遇到了麻煩，所以我傾向於同意。

根據長長數據類型是否受支持，數據存儲在包含指向uint16_t或uint32_t數組的指針的結構中。如果long long不受支持，則uint16_t用於捕獲乘法和加法操作中的任何進位/溢出。我現在的函數是加法，減法，乘法，2的補碼求反，比較和，或者xor，不是左移，右移，左旋，右旋，位反轉，幾個轉換例程，一個隨機數填充例程，以及其他一些實用程序。所有這些工作正確（我在計算器上檢查了結果），除了部門。

typedef struct bn_data_t bn_t; 
struct bn_data_t 
    { 
    uint32 sz1;   /* Bit Size */ 
    uint32 sz8;   /* Byte Size */ 
    uint32 szw;   /* Word Count */ 
    bnint *dat;   /* Data Array */ 
    uint32 flags;  /* Operational Flags */ 
    }; 

這涉及到另外一個問題，我問inline assembler，因爲這是這是什麼的。

我迄今發現：

Algorithm for dividing very large numbers

What is the fastest algorithm for division of crazy large integers?

https://en.wikipedia.org/wiki/Division_algorithm

Newton-Raphson Division With Big Integers

和一堆關於這個問題的學術論文。

我迄今爲止嘗試：

我有一個基本的日常工作，但它由單一字把一個多字的大整數。我試圖實現一個牛頓 - 拉夫遜算法，但這不起作用，因爲我得到了一些非常奇怪的結果。我知道牛頓基於它的微積分方法，但這是整數數學而不是浮點數。我理解Goldschmidt除法算法背後的數學，但我不清楚如何用整數數學實現它。部分這些算法的部分問題是它們需要基數爲2的對數函數。我知道如何使用浮點數和泰勒級數來實現對數函數，但在使用整數數學時不會。

我已經試過看GMP庫，但分割算法沒有很好的記錄，它有點超過我的頭。似乎他們在不同的點使用不同的算法，這增加了混淆。

對於學術論文，我大多瞭解數學（我已經清除基本演算數學，多變量微積分和常微分方程），但再次，存在使用我的數學知識和實施之間存在脫節整數數學。我已經看到了小學的方法被建議，從我可以確定的東西類似於減法的方法，但我不太確定如何實現那一個。有任何想法嗎？代碼會很好。

編輯：

這是我個人的學習經驗。我想了解它是如何完成的。

編輯：4-JUN-2016

它已經一段時間，因爲我已經在這工作，因爲我曾在其他火熨斗等項目上下工夫。現在我重新訪問了這個項目，我終於實現了使用兩種不同算法的大整數除法。基本的是概述here的減法方法。僅當除數爲一個字時才調用使用CPU除法指令的高速算法。這兩種算法已被證實能正常工作，因爲它們產生的結果已經用online big number calculator進行檢查。所以現在，所有基本的數學和邏輯功能都已經實現。這些功能包括加，減，乘，除，除以模數，模數，或者，不，xor，negate，reverse（反射），左移，右移，左旋和右旋。隨着他們的需求出現，我可能會添加其他功能。感謝所有回覆的人。

Answer 1

C不提供任何特殊的這種類型的部門。
如果你想解決這個問題，你需要自己實施解決方案。
我在堆棧溢出發現了一些鏈接，可以幫助您選擇適合您需求的解決方案：

What is the fastest algorithm for division of crazy large integers?

或

Division of Large numbers

Answer 2

使用了巨大的整數，例如圖書館GNU MP，NTL或FLINT。可能還有其他人。編織你自己是浪費時間。