Публикации по теме 'karatsuba'
Что такое алгоритм умножения Карацубы?
Изучение более быстрого способа умножения двух целых чисел, чем старый школьный метод.
Как посчитать 3 х 4? Очевидный ответ заключается в том, что нас заучивали наизусть во время учебы в школе, и мы знаем, что ответ равен 12. Как насчет вычисления 23 x 42, некоторые из нас могут умножать это в уме, в то время как другие используют ручку и бумагу, и мы приходим к результату 966. Что бы вы сделали, если бы я увеличил количество цифр с 3,4,… до, скажем, 60 в множителе и множимом, мы бы..
Умножение Карацубы
Я прохожу курс Разделяй и властвуй, сортировка, поиск и рандомизированные алгоритмы от Coursera. Задача на 1-ю неделю - реализовать алгоритм умножения целых чисел с использованием метода умножения Карацубы. В результате можно умножить два 64-значных числа:
Попробуйте умножить эти два числа, и вы получите
Это правильный результат, но он сильно теряет точность, потому что наибольшее целое число, которое может отобразить JavaScript, равно 2⁵³-1 ( MDN ).
Чтобы решить эту проблему,..
Вопросы по теме 'karatsuba'
Разница между встроенным в Python pow и math pow для больших целых чисел
Я обнаружил, что для больших целых чисел math.pow не удается успешно преобразовать в свою целочисленную версию. У меня возникла ошибка умножения Карацубы при реализации с math.pow.
Например:
>>> a_Size=32
>>> pow(10,a_size)...
1531 просмотров
schedule
17.10.2021
Алгоритм Карацубы без BigInteger в Java, неожиданное поведение при рекурсии
Итак, я хочу запустить алгоритм Карацубы без использования класса BigInteger в Java, поэтому, следуя псевдокоду и этот вопрос , я пришел со следующим кодом
public static long recKaratsuba(long i1, long i2){
if(i1<10 || i2<10) {...
70 просмотров
schedule
29.09.2021
Итерационный алгоритм Карацубы, распараллеленный и векторизованный с использованием OpenACC на C ++
Я пытаюсь распараллелить итеративную версию алгоритма Карацубы с помощью OpenACC на C ++. Я хотел бы спросить, как я могу векторизовать внутренний for loop . Мой компилятор показывает это сообщение об этом цикле:
526, Complex loop carried...
198 просмотров
schedule
30.07.2022
Ошибка целочисленного умножения Карацубы из-за ошибки сегментации
Когда я запускаю программу, она падает с ошибкой сегментации. Кроме того, когда я отлаживаю код в IDE codeblocks, я также не могу его отлаживать. Программа вылетает еще до начала отладки. Я не могу понять проблему. Любая помощь будет оценена по...
239 просмотров
schedule
13.09.2022
ArrayIndexOutOfBoundsException: 0 в реализации Карацубы
Я реализую алгоритм Карацубы и сталкиваюсь с этим исключением.
Некоторый соответствующий код (при необходимости я могу опубликовать больше):
Из основного:
int degree = (input.nextInt() + 1);
int A[] = new int[degree];
int B[] = new...
80 просмотров
schedule
14.09.2022
Произведение 64-значных чисел с использованием алгоритма Карацубы
Как использовать алгоритм Карацубы для вычисления произведения двух 64-значных чисел так, чтобы в умножении участвовали только однозначные числа?
1050 просмотров
schedule
22.07.2023
Рекурсивный алгоритм Карацубы, дающий неточные ответы
Я пытался реализовать алгоритм умножения Карацубы на С++ для двух больших чисел одинаковой длины. Мой код работает правильно для меньших чисел, таких как 3456*1492, но не работает с большими числами, такими как 64-значные. Обычно он получает первые...
97 просмотров
schedule
17.01.2023
Код Java-рекурсии умножения Карацубы не работает?
Я пытаюсь умножить два числа, используя умножение Карацубы. Мой java-код не работает. Я использовал строку в качестве параметров и аргументов, чтобы мы могли умножать два n-значных числа (n четно). Кроме того, я не хочу использовать long или...
1633 просмотров
schedule
22.05.2024