1 文本格式
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
/// <summary>
/// 大数的四则(加减乘除)运算
/// 及其运算符重载(取余数)
/// </summary>
public class BigNumber
{
private string Buffer { get; set; } = "";
private string Sign { get; set; } = "";
public BigNumber(int n) { Next(n); }
public BigNumber(string b, string s = "")
{
Buffer = b;
Sign = s;
}
public BigNumber Clone()
{
BigNumber r = new BigNumber(Buffer, Sign);
return r;
}
public int Length { get { return Buffer.Length; } }
/// <summary>
/// 随机生成任意长度的大数(BigNumber)
/// </summary>
/// <param name="n">位数</param>
/// <returns></returns>
public void Next(int n)
{
Random rnd = new Random();
StringBuilder sb = new StringBuilder();
sb.Append((rnd.Next(9) + 1).ToString());
for (int i = 1; i < n; i++)
{
sb.Append((rnd.Next(10)).ToString());
}
Buffer = sb.ToString();
}
/// <summary>
/// 字符串型的数字转为数组(低位(右)在前)
/// </summary>
/// <param name="a"></param>
/// <param name="n">最大位数,后面留0</param>
/// <returns></returns>
public static int[] string_to_digitals(string a, int n)
{
char[] c = a.ToCharArray();
int[] d = new int[n];
for (int i = a.Length - 1, j = 0; i >= 0; i--)
{
if (c[i] == '-') continue;
d[j++] = c[i] - '0';
}
return d;
}
/// <summary>
/// 数组型数字转为字符串型(低位(右)在前)
/// </summary>
/// <param name="d"></param>
/// <returns></returns>
public static string digitals_to_string(int[] d)
{
int n = d.Length;
int k = n - 1;
while ((k >= 0) && (d[k] == 0)) k--;
if (k >= 0)
{
StringBuilder sb = new StringBuilder();
for (; k >= 0; k--) sb.Append(d[k]);
return sb.ToString();
}
else
{
return "0";
}
}
/// <summary>
/// 大数加法 c = a + b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string big_integer_plus(string a, string b)
{
int n = Math.Max(a.Length, b.Length) + 1;
// 位数不长的数字直接计算
if (n <= 18)
{
return (ulong.Parse(a) + ulong.Parse(b)).ToString();
}
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(b, n);
int[] dc = new int[n];
Array.Copy(da, dc, n);
for (int i = 0; i < (n - 1); i++)
{
dc[i] = dc[i] + db[i];
if (dc[i] > 9)
{
dc[i] -= 10;
dc[i + 1] += 1;
}
}
return digitals_to_string(dc);
}
/// <summary>
/// 大数减法 c = a - b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string big_integer_subtract(string a, string b)
{
int na = a.Length;
int nb = b.Length;
int n = Math.Max(na, nb) + 1;
if (n <= 18)
{
return (ulong.Parse(a) - ulong.Parse(b)).ToString();
}
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(b, n);
for (int i = 0; i < na; i++)
{
da[i] -= db[i];
if (da[i] < 0)
{
da[i] += 10;
da[i + 1] -= 1;
}
}
return digitals_to_string(da);
}
/// <summary>
/// 大数乘法 c = a * b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string big_integer_multiply(string a, string b)
{
int na = a.Length;
int nb = b.Length;
int n = na + nb + 1;
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(b, n);
int[] dc = new int[n];
for (int i = 0; i < na; i++)
{
for (int j = 0; j < nb; j++)
{
dc[i + j] += da[i] * db[j];
}
}
for (int i = 0; i < n; i++)
{
if (dc[i] >= 10)
{
dc[i + 1] += (dc[i] / 10);
dc[i] %= 10;
}
}
return digitals_to_string(dc);
}
/// <summary>
/// 比较a,b的大小,返回1,0,-1
/// 数据从低位(右)往高位(左)存储;
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static int big_integer_compare(int[] a, int[] b)
{
for (int i = a.Length - 1; i >= 0; i--)
{
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
}
return 0;
}
public static int big_integer_compare(string a, string b)
{
int n = Math.Max(a.Length, b.Length);
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(a, n);
return big_integer_compare(da, db);
}
/// <summary>
/// 大数除法 c = a / b % d
/// c 为商,d 为余数。
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="d">余数</param>
/// <returns>商c</returns>
public static string big_integer_divide(string a, string b, out string d)
{
int n = a.Length;
int[] db = string_to_digitals(b, n);
string q = a;
List<string> p = new List<string>();
int[] dq = string_to_digitals(q, n);
while (big_integer_compare(dq, db) >= 0)
{
int len = q.Length - b.Length;
string v2 = b + String.Join("", new int[len]);
int[] dv = string_to_digitals(v2, n);
if (big_integer_compare(dq, dv) < 0)
{
len--;
v2 = b + String.Join("", new int[len]);
dv = string_to_digitals(v2, n);
}
string v1 = "1" + String.Join("", new int[len]);
while (big_integer_compare(dq, dv) >= 0)
{
p.Add(v1);
q = big_integer_subtract(q, v2);
dq = string_to_digitals(q, n);
}
}
d = q;
string r = p[0];
for (int i = 1; i < p.Count; i++)
{
r = big_integer_plus(r, p[i]);
}
return r;
}
#region 四则运算符(含取余数)重载
// 运算符重载是一种常用的编程技术。
// 用于支持“非数值类型的数据(比如类)”以常用的运算符 +-*/% 等等进行运算,使得代码简约直观。
// 没有运算符重载的语言(比如golang)一般都不适合数值计算。
public static BigNumber operator +(BigNumber a, BigNumber b)
{
return new BigNumber(big_integer_plus(a.Buffer, b.Buffer));
}
public static BigNumber operator -(BigNumber a, BigNumber b)
{
if (a > b || a == b)
return new BigNumber(big_integer_subtract(a.Buffer, b.Buffer));
else
return new BigNumber(big_integer_subtract(b.Buffer, a.Buffer), "-");
}
public static BigNumber operator *(BigNumber a, BigNumber b)
{
return new BigNumber(big_integer_multiply(a.Buffer, b.Buffer));
}
public static BigNumber operator /(BigNumber a, BigNumber b)
{
return new BigNumber(big_integer_divide(a.Buffer, b.Buffer, out string _));
}
public static BigNumber operator %(BigNumber a, BigNumber b)
{
string c = big_integer_divide(a.Buffer, b.Buffer, out string d);
return new BigNumber(d);
}
public static bool operator >(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) > 0;
}
public static bool operator <(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) < 0;
}
public static bool operator ==(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) == 0;
}
public static bool operator !=(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) != 0;
}
public static bool Equals(BigNumber a, BigNumber b) { return (a == b); }
public override string ToString()
{
return Sign + Buffer;
}
#endregion
}
2 代码格式
using System;
using System.Text;
using System.Collections;
using System.Collections.Generic;
/// <summary>
/// 大数的四则(加减乘除)运算
/// 及其运算符重载(取余数)
/// </summary>
public class BigNumber
{
private string Buffer { get; set; } = "";
private string Sign { get; set; } = "";
public BigNumber(int n) { Next(n); }
public BigNumber(string b, string s = "")
{
Buffer = b;
Sign = s;
}
public BigNumber Clone()
{
BigNumber r = new BigNumber(Buffer, Sign);
return r;
}
public int Length { get { return Buffer.Length; } }
/// <summary>
/// 随机生成任意长度的大数(BigNumber)
/// </summary>
/// <param name="n">位数</param>
/// <returns></returns>
public void Next(int n)
{
Random rnd = new Random();
StringBuilder sb = new StringBuilder();
sb.Append((rnd.Next(9) + 1).ToString());
for (int i = 1; i < n; i++)
{
sb.Append((rnd.Next(10)).ToString());
}
Buffer = sb.ToString();
}
/// <summary>
/// 字符串型的数字转为数组(低位(右)在前)
/// </summary>
/// <param name="a"></param>
/// <param name="n">最大位数,后面留0</param>
/// <returns></returns>
public static int[] string_to_digitals(string a, int n)
{
char[] c = a.ToCharArray();
int[] d = new int[n];
for (int i = a.Length - 1, j = 0; i >= 0; i--)
{
if (c[i] == '-') continue;
d[j++] = c[i] - '0';
}
return d;
}
/// <summary>
/// 数组型数字转为字符串型(低位(右)在前)
/// </summary>
/// <param name="d"></param>
/// <returns></returns>
public static string digitals_to_string(int[] d)
{
int n = d.Length;
int k = n - 1;
while ((k >= 0) && (d[k] == 0)) k--;
if (k >= 0)
{
StringBuilder sb = new StringBuilder();
for (; k >= 0; k--) sb.Append(d[k]);
return sb.ToString();
}
else
{
return "0";
}
}
/// <summary>
/// 大数加法 c = a + b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string big_integer_plus(string a, string b)
{
int n = Math.Max(a.Length, b.Length) + 1;
// 位数不长的数字直接计算
if (n <= 18)
{
return (ulong.Parse(a) + ulong.Parse(b)).ToString();
}
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(b, n);
int[] dc = new int[n];
Array.Copy(da, dc, n);
for (int i = 0; i < (n - 1); i++)
{
dc[i] = dc[i] + db[i];
if (dc[i] > 9)
{
dc[i] -= 10;
dc[i + 1] += 1;
}
}
return digitals_to_string(dc);
}
/// <summary>
/// 大数减法 c = a - b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string big_integer_subtract(string a, string b)
{
int na = a.Length;
int nb = b.Length;
int n = Math.Max(na, nb) + 1;
if (n <= 18)
{
return (ulong.Parse(a) - ulong.Parse(b)).ToString();
}
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(b, n);
for (int i = 0; i < na; i++)
{
da[i] -= db[i];
if (da[i] < 0)
{
da[i] += 10;
da[i + 1] -= 1;
}
}
return digitals_to_string(da);
}
/// <summary>
/// 大数乘法 c = a * b
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static string big_integer_multiply(string a, string b)
{
int na = a.Length;
int nb = b.Length;
int n = na + nb + 1;
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(b, n);
int[] dc = new int[n];
for (int i = 0; i < na; i++)
{
for (int j = 0; j < nb; j++)
{
dc[i + j] += da[i] * db[j];
}
}
for (int i = 0; i < n; i++)
{
if (dc[i] >= 10)
{
dc[i + 1] += (dc[i] / 10);
dc[i] %= 10;
}
}
return digitals_to_string(dc);
}
/// <summary>
/// 比较a,b的大小,返回1,0,-1
/// 数据从低位(右)往高位(左)存储;
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <returns></returns>
public static int big_integer_compare(int[] a, int[] b)
{
for (int i = a.Length - 1; i >= 0; i--)
{
if (a[i] > b[i]) return 1;
else if (a[i] < b[i]) return -1;
}
return 0;
}
public static int big_integer_compare(string a, string b)
{
int n = Math.Max(a.Length, b.Length);
int[] da = string_to_digitals(a, n);
int[] db = string_to_digitals(a, n);
return big_integer_compare(da, db);
}
/// <summary>
/// 大数除法 c = a / b % d
/// c 为商,d 为余数。
/// </summary>
/// <param name="a"></param>
/// <param name="b"></param>
/// <param name="d">余数</param>
/// <returns>商c</returns>
public static string big_integer_divide(string a, string b, out string d)
{
int n = a.Length;
int[] db = string_to_digitals(b, n);
string q = a;
List<string> p = new List<string>();
int[] dq = string_to_digitals(q, n);
while (big_integer_compare(dq, db) >= 0)
{
int len = q.Length - b.Length;
string v2 = b + String.Join("", new int[len]);
int[] dv = string_to_digitals(v2, n);
if (big_integer_compare(dq, dv) < 0)
{
len--;
v2 = b + String.Join("", new int[len]);
dv = string_to_digitals(v2, n);
}
string v1 = "1" + String.Join("", new int[len]);
while (big_integer_compare(dq, dv) >= 0)
{
p.Add(v1);
q = big_integer_subtract(q, v2);
dq = string_to_digitals(q, n);
}
}
d = q;
string r = p[0];
for (int i = 1; i < p.Count; i++)
{
r = big_integer_plus(r, p[i]);
}
return r;
}
#region 四则运算符(含取余数)重载
// 运算符重载是一种常用的编程技术。
// 用于支持“非数值类型的数据(比如类)”以常用的运算符 +-*/% 等等进行运算,使得代码简约直观。
// 没有运算符重载的语言(比如golang)一般都不适合数值计算。
public static BigNumber operator +(BigNumber a, BigNumber b)
{
return new BigNumber(big_integer_plus(a.Buffer, b.Buffer));
}
public static BigNumber operator -(BigNumber a, BigNumber b)
{
if (a > b || a == b)
return new BigNumber(big_integer_subtract(a.Buffer, b.Buffer));
else
return new BigNumber(big_integer_subtract(b.Buffer, a.Buffer), "-");
}
public static BigNumber operator *(BigNumber a, BigNumber b)
{
return new BigNumber(big_integer_multiply(a.Buffer, b.Buffer));
}
public static BigNumber operator /(BigNumber a, BigNumber b)
{
return new BigNumber(big_integer_divide(a.Buffer, b.Buffer, out string _));
}
public static BigNumber operator %(BigNumber a, BigNumber b)
{
string c = big_integer_divide(a.Buffer, b.Buffer, out string d);
return new BigNumber(d);
}
public static bool operator >(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) > 0;
}
public static bool operator <(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) < 0;
}
public static bool operator ==(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) == 0;
}
public static bool operator !=(BigNumber a, BigNumber b)
{
return big_integer_compare(a.Buffer, b.Buffer) != 0;
}
public static bool Equals(BigNumber a, BigNumber b) { return (a == b); }
public override string ToString()
{
return Sign + Buffer;
}
#endregion
}