Всем привет. Может кто-то подсказать описание хорошего алгоритма умножения длиннных чисел ? Желательно с примерами работы алгоритма. Необходимо за время ~ 1c. перемножить несколько сотен длинных чисел (100-6000 знаков) на 3-4-х значные числа. Простой столбик в этом время не укладывается
-TarasBer-
6.03.2011 16:09
Надо умножить длинное на короткое? Алгоритм оптимизировать тут некуда. Если столбик не очень далеко не укладывается, то оптимизируй код: храни все числа в бинарном виде (ну то есть не цифры храни, а блоки по 4 байта от каждого), после каждого умножения запоминай старое значение edx и прибавляй к следующему результату.
Lapp
6.03.2011 17:17
Думаю, кроме столбика все равно ничего нет. Другой вопрос - КАК ты хранишь числа и как организовыван счет. Тут много ресурсов для оптимизации..
klem4
8.03.2011 14:03
Буду рад любым подсказкам, числа храню в массиве (vector), вот пример умножения факториала 1110 на 1111 (получение 1111!)
Время одного умножения слишком большое(для решения моей задачи): $ g++ -o forum forum.cpp && time ./forum real 0m0.021s user 0m0.016s sys 0m0.004s
Если нужны пояснения к коду, приведу. Комменты общие сейчас поставлю.
#include <vector>#include <string>#include <stdio.h>usingnamespacestd;
typedefvector<int> Int;
typedefvector<Int> Ints;
// создание длинного числа из строки или целого
Int create( string s );
Int create( int n );
// печать длинного числа с переводом строки или без
void dump( Int a, bool cr );
// сложить два длинных с учетом сдвига второго относительно первого на shift влево
Int add(Int, Int, int shift);
// результат сложения массива длинных Ints (каждое последующее суммируется со сдвигом = сдвиг предыдущего + 1)
Int add_multi(Ints adds);
// умножить длинное на целое < 10
Int mult(Int, int);
// умножить длинное на длинное
Int mult(Int, Int);
int main()
{
Int a = create (& quot;145685245062266955405470957253929395052590595389527229775646520190327903725540078984001841599012367729472107993412326108331941736858647087213167939319096172202654203971290399402660077112819095333290735109809509332571223574236651896501036571646308576256679272529325332526486576675624833429362316874934756651946649134214106330952600605372028076134312752959364803245907690211821900808818743276656508258321800558706776871611980343379834903596431040360678973727476691164111952173746180656971020016031834607226074608594179294098389656489920957213783176615357614143591156698768910739852091316322673365695352314024388290770769422412542668732393385146647685038265124292168312651278617036334215234804127442738817219655064945504401632115036773889846308182465643456178540901589017145380088890788421309831606431642264613513881084848351119459231765116905404081215669111479352242539206765511864730847507850802883425339785772614390190635404212687648527845665489365606249925314050447252977272210708850546544885414450253552644077861793760271638336853880909060421556157711223517977466648956776878276800459446068196549934454637751050306244441214183297010876412795686173471736463067644502648187924594344242616584409607611262493119341070227211745826733087220725629450421909884069575797597455107505821246211463362782296305164580568390083699804165472879385125900947016692348211732338420149231464765073927548513134251930993436222635303629631856880715239108287498012708422343976153016889113943927273447360011554333301306939682348088452729905758438762839041260479884792204098146400693067605375932901179113145457464529493405338204188530057122580420434243130373057556084937683183471152548366889237543023265026366216328132203543393012960988307772319594027441112056698283444243265160316444272796437726945908569827685312585288549720028775022255923623404890500096707172157799571112623166457134434281678949228778057906021255175786580221591354705444711155740006547334931711056824872216863537059642129801584847265791171095033358865645589562507086407767895673889722162765887941894649736711900228779524948275647897528244034271076502924441603323468034658887178866333029287771195112527078841067793183006671733289181877681317209401908042137605998301921907449818635479782500922195718740128180713271982084658305612624765208278129103133148238578797705624479109077726493214018938461758575162570015561269844731503247439769553709097380198114867832246304778402509061034345682207861345822729165491122453539190230833073670813175689908014990848245098712363384380053514230398317962669689851259380525047977859580222615997136593398990464572699189839891096531879871988846037460582400000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000");
Int b = create("1111");
Int r = mult(a, b);
//dump(r, true);
return0;
}
Int create( string s )
{
Int result;
for (longlong i = 0; i < s.length(); i++ )
result.push_back((longlong)(s[i]) - (longlong)'0');
return result;
}
void dump( Int a, bool cr )
{
for (longlong i = 0; i < a.size(); i++ )
printf("%d", a[i]);
if ( cr )
printf ("\n");
}
Int mult(Int a, int n)
{
Int result;
int a_size = a.size();
int bonus = 0;
for (int i = a_size - 1; i >= 0; i-- )
{
int value = bonus + a[i] * n;
if ( value >= 10 )
{
bonus = (int)(value / 10);
value %= 10;
}
else
{
bonus = 0;
}
result.insert(result.begin(), value);
}
if ( bonus > 0 )
{
result.insert(result.begin(), bonus);
}
return result;
}
Int mult(Int a, Int b)
{
Int result;
Ints adds;
int power = 0;
while ( a[a.size() - 1] == 0 )
{
a.pop_back();
++power;
}
while ( b[b.size() - 1] == 0 )
{
b.pop_back();
++power;
}
int a_size = a.size();
int b_size = b.size();
int t = 0;
for (int i = b_size - 1; i >= 0; i-- )
adds.push_back( mult(a, b[i]) );
result = add_multi( adds );
while ( power-- > 0 )
result.push_back(0);
return result;
}
Int add_multi(Ints adds )
{
Int result;
int ads_size = adds.size();
int idxs[ ads_size ];
for (int i = 0; i < ads_size; i++ )
idxs[i] = -i;
int digits_count = adds[0].size();
int bonus = 0;
bool add;
do
{
int digit_value = bonus;
add = false;
for (int j = 0; j < ads_size; j++ )
{
if ( idxs[j] >= 0 && idxs[j] < adds[j].size() )
{
digit_value += adds[j][adds[j].size() - idxs[j] - 1];
add = true;
}
++idxs[j];
}
if ( digit_value >= 0 )
{
bonus = digit_value / 10;
digit_value = digit_value % 10;
}
else
{
bonus = 0;
}
if ( digit_value > 0 || add )
result.insert(result.begin(), digit_value);
} while ( add );
if ( bonus > 0 )
{
result.push_back(bonus);
}
return result;
}
Int add(Int a, Int b, int shift)
{
Int result;
int a_size = a.size() - 1;
int b_size = b.size() - 1;
while ( shift-- > 0 )
{
result.insert(result.begin(), a[a_size--]);
}
int bonus = 0;
while (( a_size >= 0 ) && ( b_size >= 0 ))
{
int value = bonus + a[a_size--] + b[b_size--];
if ( value >= 10 )
{
value -= 10;
bonus = 1;
}
else
{
bonus = 0;
}
result.insert(result.begin(), value);
}
while ( a_size >= 0 )
{
int value = a[a_size];
if ( bonus == 1 )
{
++value;
bonus = 0;
}
if ( value >= 10 )
{
value -= 10;
bonus = 1;
}
result.insert(result.begin(), value);
--a_size;
}
while ( b_size >= 0 )
{
int value = b[b_size];
if ( bonus == 1 )
{
++value;
bonus = 0;
}
if ( value >= 10 )
{
value -= 10;
bonus = 1;
}
result.insert(result.begin(), value);
--b_size;
}
if ( bonus > 0 )
result.insert(result.begin(), 1);
return result;
}
Int create( int n )
{
Int result;
do
{
result.insert(result.begin(), n % 10);
n /= 10;
} while ( n > 0 );
return result;
}
ps редактор подсветки не подружился с первой кавычкой(заменил на ")
Гость
8.03.2011 15:21
> for (int i = a_size - 1; i >= 0; i-- ) { int value = bonus + a[i] * n; if ( value >= 10 ) { bonus = (int)(value / 10); value %= 10; } else
> 10
То есть отнование системы счисления - 10? Это плохо.
Самое быстрое - основанием брать 2^32. И в процессоре есть готовая операция, которая сразу получает (a+b) mod 2^32 и (a+b) div 2^32. Правда, компилятор Борланда, например, никак не заставить это применить, насчёт компиляторов от Микрософта и Интела не знаю.
Если тебе надо, чтобы ещё и быстро выводилось, то пойди на компромисс - в качестве основния возьми 1000000000. Считаться будет медленнее, чем с 2^32, но в 9 раз быстрее, чем с 10. И, опять же, перемножить два 32-разрядных числа и поделить 64-разрядный результат на 1000000000 - это очень просто записывается на асме (тупо mul, div подряд, промежуточный 64-разрядный результат хранится в 2х регистрах, edx и eax), но невозможно заставить компилятор Борланда сделать это по-простому.
volvo
8.03.2011 15:35
Кстати, Андрей, в твоем конкретном случае (при умножении на 1111), ты делаешь 4 раза одну и ту же работу, вот тут:
Цитата
for (int i = b_size - 1; i >= 0; i-- )
adds.push_back( mult(a, b[i]) );
Сделай чуть более хитро: опиши вектор из Int-ов, от 0 до 9, и когда приходишь в mult, проверяй, не делал ли ты уже этого умножения. Если делал - то сразу возвращай соотв. вектор. Не делал - делай, и запоминай, в следующий раз вернешь, когда понадобится. Так сэкономишь кучу времени. А если умножаешь на 1 - то можно вообще сразу возвращать исходный a, без холостых действий.
Цитата
И в процессоре есть готовая операция, которая сразу получает (a+b) mod 2^32 и (a+b) div 2^32.
Как называется?
-TarasBer-
8.03.2011 15:44
> Как называется?
Там опечатка, не +, а * надо.
klem4
10.03.2011 2:52
Спасибо за советы, volvo - хорошее замечание, воспользуюсь. Но видимо без перевода в СС с большим основанием никак сильно не ускорить. Хотя тут придется реализовывать ф-ю деления большого на большое, для перевода большого в новую СС, попробую на днях.
TarasBer
10.03.2011 15:19
> Хотя тут придется реализовывать ф-ю деления большого на большое
Надо только функцию, которая говорит частное и остаток деления a*b на 1000000000 Функция из 3 строчек на асме.
Для Д7 это выглядит так:
type TDivMod = record
d, m: cardinal;
end;
function GetDivMod(a, b: cardinal): TDivMod;
asm
mul edx
mov ecx, 1000000000
div ecx
// эти две строчки из-за того, что результат почему-то возвращается не в edx:eax, а на стеке
mov ebp - $18, eax
mov ebp - $14, edx
end
(Можно и через int64 написать, но это тормозить будет).
Ещё можно её модифицировать, чтобы она сразу для a*b+c говорила, только не забудь про случай переноса при сложении.
klem4
10.03.2011 22:13
Дык не получится так просто, в cardinal ты число из 5000 цифр не запишешь я думаю.
-TarasBer-
10.03.2011 23:06
Это просто для замены
Код
int value = bonus + a[i] * n; if ( value >= 10 ) { bonus = (int)(value / 10); value %= 10; }
На
Код
(value, bonus) = MulDiv(a[i], n);
Не надо основание системы счисления менять на 10^500, это для 1000000000.
А функция деления длинного на длинное тебе не нужна, ты ж не собрался, надеюсь, основание длинным делать. Число храни как массив cardinal (или u32 или uint32, или что там), каждый элемент от 0 до 999999999. Ну просто чтобы было проще выводить результат. Иначе бы можно было бы тупо взять в качестве основания 2^32 и не париться.
Ещё такой момент - то, что результат возвращается на стеке, а не в регистрах, тоже не очень хорошо. Было бы хорошо, если было можно своё соглашение о вызове описать, но я хз, как в С++ с этим.
klem4
15.03.2011 1:50
Большое спасибо за подсказки, все получилось, использовал хранение в СС с основанием 10^8. Задача собственно заключалась в следующем: дано число, являющееся факториалом N, где 1 <= N <= 2000. Определить надо N.
Это текстовая версия — только основной контент. Для просмотра полной версии этой страницы, пожалуйста, нажмите сюда.