Описание тега karatsuba
Асимптотически быстрый алгоритм умножения больших целых чисел. Понимание этого алгоритма и его реализаций.
1
ответ
Реализация умножения Карацубы в Java BigDecimal
Недавно я пытался реализовать умножение Карацубы для больших чисел. Затем я попытался сравнить мою реализацию с реализацией Java BigInteger. Я не мог следовать этой строке кода: // result = p1 * 2^(32*2*half) + (p3 - p1 - p2) * 2^(32*half) + p2 BigI…
09 янв '17 в 07:09
1
ответ
Как бы вы, где один алгоритм предпочтительнее, чем другой алгоритм
Я пытаюсь сравнить два алгоритма и их эффективность. Я пытаюсь найти значение для n, где один алгоритм становится более эффективным, чем другой алгоритм. Любые полезные примеры или ресурсы будут огромной помощью.
25 ноя '17 в 16:35
1
ответ
Я хочу реализовать умножение Карацубы в Python
Я хочу реализовать умножение Карацубы в Python. Но я получаю правильный ответ, когда число большое. Может кто-нибудь сказать мне, где мой код не так？ Реализация умножения Карацубы неверна, когда х очень большой. import math def fun1(x,y): if x <=…
17 июл '18 в 05:05
3
ответа
При реализации алгоритма Карацубы метод подсчитывает только малые числа, но большой ответ не верен, в чем проблема?
Реализация алгоритма Карацуба, метод считает только маленькие числа, правда, но большой ответ не является правильным, в чем проблема? var x = "1685287499328328297814655639278583667919355849391453456921116729"; var y = "711419284857775458796974462655…
15 янв '19 в 15:23
1
ответ
Произведение 64-значных чисел с использованием алгоритма Карацубы
Как использовать алгоритм Карацубы для вычисления произведения двух 64-значных чисел таким образом, чтобы в умножении принимали участие только однозначные числа?
23 дек '16 в 14:30
1
ответ
Алгоритм Карацубы для умножения полиномов
Я пытаюсь реализовать рекурсивный алгоритм Карацубы для умножения двух полиномов (одинаковой степени). Мой код все еще не работает для полиномов со степенью выше 1. Может ли кто-нибудь объяснить мне, что я делаю неправильно в своей функции? Он долже…
14 мар '18 в 21:56
1
ответ
Ошибка при реализации алгоритма Карацубы с BigInteger
Я пытаюсь реализовать алгоритм karatsuba с помощью Java, предъявляя иск BigInteger, я выполнил все шаги, но не получаю правильный результат, что сводит меня с ума. Вот мой код: public BigInteger karatsuba(BigInteger a, BigInteger b, int base) { if (…
04 фев '17 в 00:36
1
ответ
Карацуба - умножение полиномов с помощью CUDA
Я использую CUDA для итеративного алгоритма Карацубы, и я хотел бы спросить, почему одна строка всегда вычисляется по-разному. Сначала я реализовал эту функцию, которая всегда правильно вычисляла результат: __global__ void kernel_res_main(TYPE *A, T…
25 апр '18 в 20:17
2
ответа
Функция возвращает 0 при умножении каратсуба
Я пытаюсь реализовать умножение Карацубы с помощью рекурсивных вызовов. Код ниже должен работать, но я продолжаю получать ноль в качестве ответа. Какие-нибудь мысли? #define ll long long int ll kmul(ll p, ll q) { ll a,b,c,d,ans; ll n=0; while(p) { p…
23 окт '16 в 17:48
1
ответ
Реализация рекурсивной функции Карацубы в классе Python, ошибки
Ранее я опубликовал вопрос на эту тему, и на него ответили довольно хорошо. Реализация функции сортировки слиянием в классе Python, ошибки И все же есть еще кое-что, что ускользает от меня в отношении рекурсии в классе. В приведенной выше проблеме, …
09 июн '18 в 13:51
0
ответов
Умножение полиномов Карацубы с использованием Python
Я пытаюсь реализовать код для умножения 2-х полиномов с использованием алгоритма Карацубы, я нашел этот код для умножения 2-х целых чисел с помощью метода Картасубы, однако я не могу отредактировать его, чтобы иметь возможность использовать нескольк…
06 июл '18 в 01:35
0
ответов
Ошибка времени выполнения:- превышена максимальная глубина рекурсии по сравнению
Я знаю, что подобные вопросы уже задавались, но я застрял с этой проблемой умножения длинных целых чисел.для большого размера ввода. import math import sys def karatsuba(num1,num2): y = 10 if num1<y or num2<y : return num1*num2 m1 = int(math.l…
18 окт '17 в 21:09
1
ответ
Алгоритм Карацубы
Я продолжаю получать эти ошибки при запуске своей программы, кто-нибудь может обнаружить ошибку? У меня нет опыта использования рекурсии, и я мог испортить базовый сценарий. Мое тестирование состоит из двух чисел одинаковой длины, и моя цель - умнож…
03 июл '17 в 01:17
1
ответ
Ошибка алгоритма Карацубы
Я делаю реализацию karatsuba, но у меня есть эта ошибка: java.lang.NumberFormatException: Zero length BigInteger at java.math.BigInteger.<init>(BigInteger.java:296) at java.math.BigInteger.<init>(BigInteger.java:476) at com.Karatsuba.res…
12 ноя '16 в 19:37
1
ответ
Итеративный алгоритм Карацубы распараллелен и векторизован с использованием OpenACC в C++
Я пытаюсь распараллелить итерационную версию алгоритма Карацубы, используя OpenACC в C++. Я хотел бы спросить, как я могу векторизовать внутренний for loop, Мой компилятор показывает мое сообщение об этом цикле: 526, Complex loop carried dependence …
13 апр '18 в 12:48
8
ответов
Реализация умножения Карацубы
Недавно я применил умножение Карацубы как личное упражнение. Я написал свою реализацию на Python, следуя псевдокоду, представленному в Википедии: процедура каратсуба (номер1, номер2) если (num1 < 10) или (num2 < 10) вернуть num1*num2 /* вычисляет ра…
19 фев '17 в 06:40
1
ответ
Разница между встроенным в Python pow и math pow для больших целых чисел
Я считаю, что для больших целых чисел math.pow не может успешно преобразоваться в целочисленную версию. Я получил ошибочное умножение Карацубы при реализации с math.pow. Например: >>> a_Size=32 >>> pow(10,a_size) * 1024 10240000000…
10 окт '16 в 14:10
2
ответа
Произведение двух комплексных чисел менее чем в 3 умножениях
Может кто-нибудь сломать это для меня? Почему это не может быть сделано в двух умножениях? Умножение комплексных чисел Если число умножений, необходимое для вычисления, рассматривается как мера его сложности, и эти вычисления выполняются с использов…
29 ноя '16 в 03:25
0
ответов
Каратсуба умножение имеет ошибку с большим числом
Я написал одну версию моего кода Python. Базовые тестовые примеры кажутся хорошими, в то время как случай с очень большим числом karatsuba(3141592653589793238462643383279502884197169399375105820974944592, 27182818284590452353602874713526624977572470…
03 июн '18 в 12:16
2
ответа
Завершается сигналом SIGSEGV (Ошибка границы адреса) в рекурсивной функции
Я пытаюсь реализовать алгоритм Карацубы для умножения. Я вроде следую за псевдокодом на этой вики- странице. Но я всегда получаю эту ошибку: завершается сигналом SIGSEGV (ошибка границы адреса) Когда я заменил строки, которые вызывают рекурсию, чем-…
22 авг '16 в 20:47