Всем привет. Может кто-то подсказать описание хорошего алгоритма умножения длиннных чисел ? Желательно с примерами работы алгоритма. Необходимо за время ~ 1c. перемножить несколько сотен длинных чисел (100-6000 знаков) на 3-4-х значные числа. Простой столбик в этом время не укладывается
--------------------
perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
using namespace std; typedef vector<int> Int; typedef vector<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;145685245062266955405470957253929395052590595389527229775646520190327903725 54007898400184159901236772947210799341232610833194173685864708721316793931909617 22026542039712903994026600771128190953332907351098095093325712235742366518965010 36571646308576256679272529325332526486576675624833429362316874934756651946649134 21410633095260060537202807613431275295936480324590769021182190080881874327665650 82583218005587067768716119803433798349035964310403606789737274766911641119521737 46180656971020016031834607226074608594179294098389656489920957213783176615357614 14359115669876891073985209131632267336569535231402438829077076942241254266873239 33851466476850382651242921683126512786170363342152348041274427388172196550649455 04401632115036773889846308182465643456178540901589017145380088890788421309831606 43164226461351388108484835111945923176511690540408121566911147935224253920676551 18647308475078508028834253397857726143901906354042126876485278456654893656062499 25314050447252977272210708850546544885414450253552644077861793760271638336853880 90906042155615771122351797746664895677687827680045944606819654993445463775105030 62444412141832970108764127956861734717364630676445026481879245943442426165844096 07611262493119341070227211745826733087220725629450421909884069575797597455107505 82124621146336278229630516458056839008369980416547287938512590094701669234821173 23384201492314647650739275485131342519309934362226353036296318568807152391082874 98012708422343976153016889113943927273447360011554333301306939682348088452729905 75843876283904126047988479220409814640069306760537593290117911314545746452949340 53382041885300571225804204342431303730575560849376831834711525483668892375430232 65026366216328132203543393012960988307772319594027441112056698283444243265160316 44427279643772694590856982768531258528854972002877502225592362340489050009670717 21577995711126231664571344342816789492287780579060212551757865802215913547054447 11155740006547334931711056824872216863537059642129801584847265791171095033358865 64558956250708640776789567388972216276588794189464973671190022877952494827564789 75282440342710765029244416033234680346588871788663330292877711951125270788410677 93183006671733289181877681317209401908042137605998301921907449818635479782500922 19571874012818071327198208465830561262476520827812910313314823857879770562447910 90777264932140189384617585751625700155612698447315032474397695537090973801981148 67832246304778402509061034345682207861345822729165491122453539190230833073670813 17568990801499084824509871236338438005351423039831796266968985125938052504797785 95802226159971365933989904645726991898398910965318798719888460374605824000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000"); Int b = create("1111");
Int r = mult(a, b); //dump(r, true);
return 0; }
Int create( string s ) { Int result; for (long long i = 0; i < s.length(); i++ ) result.push_back((long long)(s[i]) - (long long)'0'); return result; }
void dump( Int a, bool cr ) { for (long long 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); }