我真的很想制作自己的库来处理大量数据。我开始做。我意识到我不知道该怎么做。
public struct BigInt
{
private byte[] Value { get; set; }
public BigInt(string value)
{
if (value.Length != 0)
Value = new byte[value.Length];
else
{
Value = null;
return;
}
for (int i = value.Length - 1; i >= 0; i--)
Value[i] = (byte)value[i];
}
public BigInt(byte[] value) { this.Value = value; }
public override string ToString() => Encoding.Default.GetString(Value);
public static implicit operator BigInt(string num) => new BigInt(num);
public static implicit operator string(BigInt num) => Encoding.Default.GetString(num.Value);
public static string operator +(BigInt c1, BigInt c2) => Addition(c1.Value, c2.Value);
public static string operator +(BigInt c1, string c2) => Addition(c1.Value, Encoding.Default.GetBytes(c2));
public static string operator *(BigInt c1, BigInt c2) => Multiplication(c1.Value, c2.Value);
public static string operator *(BigInt c1, string c2) => Multiplication(c1.Value, Encoding.Default.GetBytes(c2));
public static string Addition(byte[] x, byte[] y)
{
List<byte> result = new List<byte>();
int c = 0, d = 0;
List<byte> z = new List<byte>();
if(x.Length > y.Length)
{
z.InsertRange(0, Encoding.Default.GetBytes(new String('0', x.Length - y.Length).ToCharArray()));
z.AddRange(y);
y = z.ToArray();
}
else
{
z.InsertRange(0, Encoding.Default.GetBytes(new String('0', y.Length - x.Length).ToCharArray()));
z.AddRange(x);
x = z.ToArray();
}
for(int i = x.Length-1; i>=0; i--)
{
byte a = x[i];
byte b = y[i];
c = (d + (a % 48) + (b % 48)) % 10;
result.Add((byte)c);
d = (d + a % 48 + b % 48) / 10;
}
if (d != 0)
result.Add((byte)d);
result.Reverse();
return string.Join("", result);
}
public static string Multiplication(byte[] x, byte[] y)
{
List<byte>[] result = new List<byte>[y.Length];
for (int i = 0; i < y.Length; i++)
{
int c = 0;
int d = 0;
List<byte> array = new List<byte>();
for (int j = 0; j < x.Length; j++)
{
byte a = x[x.Length - 1 - j];
byte b = y[y.Length - 1 - i];
c = (d + (a % 48) * (b % 48)) % 10;
array.Add((byte)c);
d = (d + (a % 48) * (b % 48)) / 10;
}
if (d > 0)
array.Add((byte)d);
result[i] = array;
}
for (int i = 0; i < result.Length; i++)
for (int j = 0; j < result[i].Count / 2; j++)
{
byte temp = result[i][j];
result[i][j] = result[i][result[i].Count - 1 - j];
result[i][result[i].Count - 1 - j] = temp;
}
if (result.Length > 1)
for (int i = 1; i < result.Length; i++)
for (int j = 0; j < result.Length - i; j++)
result[j + i].Add((byte)0);
if (result.Length > 1)
{
for (int i = 0; i < result.Length - 1; i++)
{
List<byte> z = result[0];
for (int j = 0; j < z.Count; j++)
z[j] += 48;
result[0] = new List<byte>(Encoding.Default.GetBytes(Addition(z.ToArray(), result[i + 1].ToArray())));
}
return Encoding.Default.GetString(result[0].ToArray());
}
return String.Join("", result[0]);
}
public static string Pow(string x, int degrees)
{
if (degrees == 0) return "1";
if (degrees == 1) return x;
byte[] result = Encoding.Default.GetBytes(x);
byte[] num = result;
for (int i = 2; i <= degrees; i++)
result = Encoding.Default.GetBytes(Multiplication(result, num));
return Encoding.Default.GetString(result);
}
public static string Factorial(int number)
{
if (number == 0) return "1";
if (number <= 2) return number.ToString();
byte[] result = Encoding.Default.GetBytes((6).ToString());
for (int i = 4; i <= number; i++)
result = Encoding.Default.GetBytes(Multiplication(result, Encoding.Default.GetBytes(i.ToString())));
return Encoding.Default.GetString(result);
}
}
以上是我想出的所有代码。而且我确信这段代码是尽可能糟糕的。
我想知道在编写这样的库时要遵循什么。(例如,将数据存储在哪里以便它需要更少的内存或使用什么算法来提高工作速度)更多的例子是可取的。(任何语言都可以)嗯,一些文学作品,这样你以后就不必问问题了。
我自己写了这个,我可以给出以下建议:
2^32
该系统。该数字将存储在数组中,而不是字节数组uint
。这样一来,您就可以优化使用内存,并且这个数字系统中的所有操作操作都会非常快。在这种情况下,字符串解析和方法会ToString
变得复杂得多。BigInt
,则不会发生这种转变。O(n^2)
,根据 Karatsuba 算法的乘法适用于O(n^1.58)
。您需要通过实验确定一种算法应该使用的乘数长度,以及另一种算法。n
数m
,结果将不会超过n + m
。您可以创建一个该长度的数组,而不再创建任何对象。我的大整数:https ://github.com/Zergatul/ZergatulLib/blob/master/Zergatul/Math/BigInteger.cs
不知何故,我还需要长算术。但是使用 GMP 是不可能的,因为没有操作系统和堆的微控制器需要很长的算法。我必须编写自己的 C++ 模板库来处理长整数。链接在这里:
https://sourceforge.net/projects/muntl/?source=frontpage&position=5
档案中还有俄语的描述。