алгоритм шёнхаге-штрассена

[Nerazumovskiy]

А если этот алгоритм портировать под 10 тичную систему, как думаете получиться, я очевидных препятствий невижу, если ктото видит то скажите сразу чтоб я *** не занимался.

[Xaositect]

Я говорю, там используется то, что в кольце целых чисел по модулю $2^n+1$ умножение на степень двойки производится быстро. Не уверен, что это хорошо обобщится на десятичный случай.

[Maslov]

Nerazumovskiy в сообщении #260667 писал(а):

А если этот алгоритм портировать под 10 тичную систему

Я думаю, имеет смысл, только если заодно и процессоры портировать, чтобы они в десятичном (или хотя бы в двоично-десятичном) коде работали.

[Nerazumovskiy]

в кольце целых чисел по модулю $10^n +1$ умножение на степень десятки производиться быстро.(уже обобщилось, как ни странно )

[Maslov]

Nerazumovskiy в сообщении #260692 писал(а):

в кольце целых чисел по модулю $10^n +1$ умножение на степень десятки производиться быстро

Умножение на степень двойки - это просто сдвиг, а умножение на степень десятки это что?

[Nerazumovskiy]

Maslov в сообщении #260691 писал(а):

Nerazumovskiy в сообщении #260667 писал(а):

А если этот алгоритм портировать под 10 тичную систему

Я думаю, имеет смысл, только если заодно и процессоры портировать, чтобы они в десятичном (или хотя бы в двоично-десятичном) коде работали.

понимаете смысл в том что у меня уже есть овое фурье и готовый карацуба, и работающий клас длинной арифметики для десятичного случая, и врятли мне так просто удастся запустить это всё в двоичной системе, поэтому я и хочу сделать финт ушами ( ведь если нереализовать двоичную систему то надо будет постоянно туду сюда бегать, что врятли будет сильно проще чем выполнять всё в 10-тичном случае).

[Maslov]

А в каком виде Вы длинные числа храните? Как последовательность десятичных цифр?

[Nerazumovskiy]

Maslov в сообщении #260694 писал(а):

Nerazumovskiy в сообщении #260692 писал(а):

в кольце целых чисел по модулю $10^n +1$ умножение на степень десятки производиться быстро

Умножение на степень двойки - это просто сдвиг, а умножение на степень десятки это что?

Да уменя уже всё есть для десятичной системы(клас длинной арифметики) ,в котором умножение на 10 это сдвиг.
З.Ы. в начале клас предназначался для $2^{32}$ системы исчисления, но в один прекрасный момент я понял что уменя всё неработает подумал что гдето напортил с переполнением и никак немог понять где, перевёл в 10тичную и всё заработало, что меня настолько удивило, что я просто забил на идею понять где же я налажал.

[Maslov]

Тогда, я думаю, особых сложностей быть не должно.

[Dongara]

А кто-нибудь занимался применением алгоритма Штрассена к перемножению матриц? Его метод требует много доп. памяти и поэтому на больших матрицах его применение проблематично. Никто не знает, удалось обойти проблему доп. памяти или нет?

[Xaositect]

Dongara в сообщении #261188 писал(а):

А кто-нибудь занимался применением алгоритма Штрассена к перемножению матриц? Его метод требует много доп. памяти и поэтому на больших матрицах его применение проблематично. Никто не знает, удалось обойти проблему доп. памяти или нет?

http://membres-liglab.imag.fr/pernet/Pu ... -dumas.pdf

[Dongara]

Xaositect в сообщении #261218 писал(а):

Dongara в сообщении #261188 писал(а):

А кто-нибудь занимался применением алгоритма Штрассена к перемножению матриц? Его метод требует много доп. памяти и поэтому на больших матрицах его применение проблематично. Никто не знает, удалось обойти проблему доп. памяти или нет?

http://membres-liglab.imag.fr/pernet/Pu ... -dumas.pdf

Спасибо.
P.S.
Посмотрел. Работу далекого 1976 года я знаю. Но и она и предложенный здесь подход работают хорошо в ассимптотике. Для реальных матриц (в смысле их размера), с которыми имеет дело нынешнее человечество, это не выход (в смысле выигрыша в скорости). Я нашел одну ссылку на русскоязычном форуме Интела по решению этой проблемы, но товарищ делиться секретом не хочет.

[Xaositect]

Dongara в сообщении #261237 писал(а):

Посмотрел. Работу далекого 1976 года я знаю. Но и она и предложенный здесь подход работают хорошо в ассимптотике. Для реальных матриц (в смысле их размера), с которыми имеет дело нынешнее человечество, это не выход (в смысле выигрыша в скорости). Я нашел одну ссылку на русскоязычном форуме Интела по решению этой проблемы, но товарищ делиться секретом не хочет.

Я думаю, несколько итераций алгоритма Штрассена, а затем использование обычного умножения, даст некоторый прирост скорости.
А какой сейчас размер матриц на практике? мне на втором курсе(три года назад) говорили про десятки тысяч, но, возможно, это была устаревшая информация.

[ИСН]

Xaositect в сообщении #261299 писал(а):

А какой сейчас размер матриц на практике?

"А какого размера средний файл на диске", угу.
В Гугле, может быть, ворочают матрицы миллиардных размеров, но они ведь всё равно не расскажут, как.

[Xaositect]

Ну да, люди так и делают: http://www.ics.uci.edu/~fastmm/FMM-Refe ... rassen.pdf Памяти вроде бы должно быть больше в константу раз, если все аккуратно написать.