Негабаритное целочисленное умножение и деление строк

алгоритм

ДоЛевая яма, об умножении и делении сверхбольших строковых целых чисел Или возьмем a1 и a2 в статье о сложении и вычитании в качестве примера (при условии, что 50 десятичных знаков числа π умножаются на105010^{50}Значение a1, e, умноженное на 30 знаков после запятой103010^{30}Значение a2), вычислите a1xa2, а значение a1/a2

  • Анализ, умножьте два числа x, y, то есть (одна цифра y, умноженная на x) + (десятая цифра y, умноженная на x) умноженная на 10 + ... + (наибольшая цифра у, умноженная на х) умноженная на сумму старшие биты~

  • Например, возьмем для примера 1035х287, то есть 7х1035 + 8х1035х10 + 2х1035х100, что является деформацией дистрибутивного закона умножения, 1035х(7+80+200)=1035х287

  • //Умножение двух чисел, длина произведения не будет превышать сумму длин двух чисел, например 9999x9999=99980001

  • Основная точка, определите, как долго результат имеет несколько ям, найдите способ разработать алгоритм и запишите правильный контент в яму.


func main(){
	str1 := "314159265358979323846264338327950288419716939937510"
	str2 :=                     "2718281828459045235360287471352"
	rs := multiply(str1,str2)
	fmt.Println(rs)
}


func multiply(str1, str2 string) string {
	l1, l2 := len(str1), len(str2)
	l := l1 + l2
	num := make([]int, l)

	for i := 0; i < l1; {

		for j := 0; j < l2; {
			num[l-i-j-1] += int(str1[l1-1-i]-'0') * int(str2[l2-1-j]-'0')
			j = j + 1
		}

		i = i + 1
	}
	//上面这段循环是核心,下面和大数加减大致都一样了~


	//从最右往左边,处理进位
	for n := l; n > 1; {
		temp := num[n-1]
		num[n-1] = num[n-1] % 10 //如35/10,得5
		num[n-2] += temp / 10    //如35/10,得3,将3加到上一位
		n = n - 1
	}

	//汇总字符串结果
	res := ""

	for _, i := range num {
		s := strconv.Itoa(i)
		res += s
	}

	//去除开头可能存在的0
	if len(res) > 1 {
		res = strings.TrimLeft(res, "0")
	}

	return res
}

результат операции:

 853973422267356706546355086954449319694770135199398255015274067614534738795213520

Нажмите здесь, чтобы увидеть больше интересных вводных алгоритмических задач

Golang реализует умножение больших чисел

Категории