Я прохожу курс Разделяй и властвуй, сортировка, поиск и рандомизированные алгоритмы от Coursera. Задача на 1-ю неделю - реализовать алгоритм умножения целых чисел с использованием метода умножения Карацубы. В результате можно умножить два 64-значных числа:
Попробуйте умножить эти два числа, и вы получите
Это правильный результат, но он сильно теряет точность, потому что наибольшее целое число, которое может отобразить JavaScript, равно 2⁵³-1 (MDN).
Чтобы решить эту проблему, мы могли бы использовать алгоритм Карацубы и BigInt prosal от комитета JavaScript T39.
В алгоритме Карацубы мы рекурсивно разбиваем каждое целое число пополам, пока оно не станет меньше 10, которое состоит из одной единственной цифры. Затем мы умножаем две однозначные цифры вместе. n - количество цифр для каждого целого числа.
Фактически, при каждом рекурсивном вызове программа будет пытаться разбить каждое число на a, b, c, d, чтобы вычислить умножение на основе имеющейся у нас формулы. Вместо того, чтобы усекать результат обычным целым числом, BigInt имеет достаточную точность, чтобы отобразить полный результат как
Надеюсь, вы найдете это полезным!
