C#，《小白学程序》第二十二课：大数的乘法（BigInteger Multiply）

1 文本格式

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

///

/// 大数的（加减乘除）四则运算、阶乘运算
/// 乘法计算包括小学生算法、Karatsuba和Toom-Cook3算法
///

public static class BigIn服务器托管网teger_Utility
{
///

/// 记录 加减乘除 的运算次数
///

public static int[] operations { get; set; } = new int[] { 0, 0, 0, 0 };

///

/// 《小白学程序》第十九课：随机数（Random）第六，随机生成任意长度的大数（BigInteger）
/// 一般可将超过9位数的数字成为“大数”。
/// 两个大数之间的四则运算用于密码学、高精度计算等应用。
/// 位数很多的浮点数可转为大数，再逆转即可。
///

///
///
public static string rand(int n)
{
// 随机数发生器
Random rnd = new Random();
StringBuilder sb = new StringBuilder();
// 第一个数字不能为0，故：0-8之间的随机数+ 1 = 1-9
sb.Append((rnd.Next(9) + 1).ToString());
// 后面 n-1 个数字为 0-9；从 1 开始计数
for (int i = 1; i {
sb.Append((rnd.Next(10)).ToString());
}
return sb.ToString();
}

///

/// 字符串型的数字转为数组
/// 低位（右）在前，比如 “123” , n=6 存为 3,2,1,_,_,_
/// n 可能大于 a 的长度；剩余位置留出来用于 进位 等。
///

///
/// 最大位数，后面留0
///
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 (a[i] == ‘-‘) continue;
// ‘0’ 字符是最小的数字字符
// 数值 = 字符 – ‘0’ ；
d[j++] = a[i] – ‘0’;
}
return d;
}

///

/// 数组型数字转为字符串型
/// 低位（右）在前，比如 3,2,1,_,_,_ 转为 “123”, n=6
/// 这是前面 string_to_digitals 的反向计算函数
/// n 可能大于 d 的长度；剩余位置留出来用于 进位 等。
///

///
///
public static string digitals_to_string(int[] d)
{
int n = d.Length;
// 数字数组 d 含有一些无效的数组；
// 因此，先从最右段开始去除无效的位置
int k = n – 1;
//for (; (k >= 0) && (d[k] == 0); k–) ;
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”;
}
}

///

/// 《小白学程序》第二十二课：大数（BigInteger）的四则运算之三，乘法
/// 大数乘法 c = a * b
/// 本算法与小学生算法基本一致，主要的区别是：
/// 小学生算法每两个位数的数字相乘后立即进位；
/// 而本程序则是先计算全部服务器托管网相乘，最后统一进位。
/// 可能出乎大家的意料！虽然很多大牛发明了多种算法，
/// 如果进行编译器自动优化，该算法居然经常是最快的。
///

///
///
///
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 {
for (int j = 0; j {
dc[i + j] += da[i] * db[j];
}
}
// 所有位置进位
for (int i = 0; i {
if (dc[i] >= 10)
{
dc[i + 1] += (dc[i] / 10);
dc[i] %= 10;
}
}

return digitals_to_string(dc);
}
}

2 代码格式

using System;
using System.Linq;
using System.Text;
using System.Collections.Generic;

/// 

/// 大数的（加减乘除）四则运算、阶乘运算
/// 乘法计算包括小学生算法、Karatsuba和Toom-Cook3算法
/// 
public static class BigInteger_Utility
{
    /// 

    /// 记录 加减乘除 的运算次数
    /// 
    public static int[] operations { get; set; } = new int[] { 0, 0, 0, 0 };

    /// 

    /// 《小白学程序》第十九课：随机数（Random）第六，随机生成任意长度的大数（BigInteger）
    /// 一般可将超过9位数的数字成为“大数”。
    /// 两个大数之间的四则运算用于密码学、高精度计算等应用。
    /// 位数很多的浮点数可转为大数，再逆转即可。
    /// 
    /// 
    /// 
    public static string rand(int n)
    {
        // 随机数发生器
        Random rnd = new Random();
        StringBuilder sb = new StringBuilder();
        // 第一个数字不能为0，故：0-8之间的随机数+ 1 = 1-9
        sb.Append((rnd.Next(9) + 1).ToString());
        // 后面 n-1 个数字为 0-9；从 1 开始计数
        for (int i = 1; i 
    /// 字符串型的数字转为数组
    /// 低位（右）在前，比如 "123" , n=6 存为 3,2,1,_,_,_
    /// n 可能大于 a 的长度；剩余位置留出来用于 进位 等。
    /// 
    /// 
    /// 最大位数，后面留0
    /// 
    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 (a[i] == '-') continue;
            // '0' 字符是最小的数字字符
            // 数值 = 字符 - '0' ；
            d[j++] = a[i] - '0';
        }
        return d;
    }

    /// 

    /// 数组型数字转为字符串型
    /// 低位（右）在前，比如 3,2,1,_,_,_ 转为 "123", n=6
    /// 这是前面 string_to_digitals 的反向计算函数
    /// n 可能大于 d 的长度；剩余位置留出来用于 进位 等。
    /// 
    /// 
    /// 
    public static string digitals_to_string(int[] d)
    {
        int n = d.Length;
        // 数字数组 d 含有一些无效的数组；
        // 因此，先从最右段开始去除无效的位置
        int k = n - 1;
        //for (; (k >= 0) && (d[k] == 0); k--) ;
        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";
        }
    }

    /// 

    /// 《小白学程序》第二十二课：大数（BigInteger）的四则运算之三，乘法
    /// 大数乘法 c = a * b
    /// 本算法与小学生算法基本一致，主要的区别是：
    ///     小学生算法每两个位数的数字相乘后立即进位；
    ///     而本程序则是先计算全部相乘，最后统一进位。
    /// 可能出乎大家的意料！虽然很多大牛发明了多种算法，
    /// 如果进行编译器自动优化，该算法居然经常是最快的。
    /// 
    /// 
    /// 
    /// 
    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 = 10)
            {
                dc[i + 1] += (dc[i] / 10);
                dc[i] %= 10;
            }
        }

        return digitals_to_string(dc);
    }
}

3 计算结果

服务器托管，北京服务器托管，服务器租用 http://www.fwqtg.net

相关推荐: Java静态类

在Java中，静态类是一种特殊的类，它不能被实例化。静态类主要用于工具类或实现某些特定功能，例如工厂模式中的工厂类。 要声明一个静态类，可以使用static关键字，如下所示： java复制代码 public static class StaticClass {…