如何在程序中逐位进行除法?
2022-09-04 22:48:47
我正在编写一个类似于mpz(C)或BigInteger(Java)的类。这只是为了好玩,所以请不要继续说我不应该写我自己的。
我有一个类似于:
public class HugeInt
{
public List<Integer> digits;
public HugeInt(String value)
{
// convert string value into its seperate digits.
// store them in instance variable above
}
}
现在,执行此类的add()和addtract()方法非常简单。下面是一个示例:
private List<Integer> add(List<Integer> a, List<Integer> b)
{
List<Integer> smallerDigits = (compareDigits(a,b) < 0) ? a : b;
List<Integer> largerDigits = (compareDigits(a,b) >= 0) ? a : b;
List<Integer> result = new ArrayList<Integer>();
int carry = 0;
for(int i = 0; i < largerDigits.size(); i++)
{
int num1 = largerDigits.get(i);
int num2 = (i < smallerDigits.size()) ? smallerDigits.get(i) : 0;
result.add((num1 + num2 + carry) % 10);
carry = ((num1 + num2 + carry) / 10);
}
if (carry != 0) result.add(carry);
return result;
}
同样,做乘法也不是那么难。
我在维基百科上看到有一个关于除法算法的页面,但我不确定哪一个适合我正在尝试做的事情。
因为这些正整数(表示为数字)可以任意长,所以我想确保我不会尝试在逐位以外的任何事情上执行任何操作。
但是,任何人都可以为我指出正确的方向,以便对表示为的两个数字进行除法?另外,我可以忽略余数,因为这是整数除法。List
<Integer
>