[ 3 / biz / cgl / ck / diy / fa / ic / jp / lit / sci / vr / vt ] [ index / top / reports ] [ become a patron ] [ status ]
2023-11: Warosu is now out of extended maintenance.

/sci/ - Science & Math

View post   
File: 268 KB, 600x798, 1275269256439.jpg [View same] [iqdb] [saucenao] [google]
1108667 No.1108667 [Reply] [Original]

What's the best multiplication algorithm?

>> No.1108681

Repeated addition.

>> No.1108743

>>1108681
thread\

>> No.1108771

It uses FFTs over finite fields.

>> No.1108816
File: 40 KB, 486x539, Screenshot.png [View same] [iqdb] [saucenao] [google]
1108816

>> No.1108825

int multiply(int a, int b)
{
return a*b;
}

>> No.1108857

>>1108825
enjoy you're overflow

>> No.1108869

>>1108857

Is that a threat?

>> No.1108871

>>1108857
why would i have overflow?

>> No.1108875

>>1108667
Love.

>> No.1108879

>>1108871
> herp

>> No.1108881

>>1108875
shitty runtime tho

>> No.1108890

>>1108879
>>1108871
its just an algorithm. there is no data representation that will guarantee no everflow. i used int just to demsontrate.

>> No.1108897

>>1108871
fucking noob.

int only holds numbers with magnitude less than 2.147 billion (in C/C++) so if you try to multiply 1 billion times 2 billion you will get an error.

>> No.1108901

>>1108890
yes there is, given infinite computer processing space you can construct an algorithm in c++ with dynamic memory allocation that can handle any size numbers

>> No.1108902

>>1108897
you are the noob
see
>>1108890

>> No.1108904

>>1108902
no, you are the noob. see
>>1108901

>> No.1108910

>>1108904
>>1108901
>infinite computer processing space
herp

and even if you construct this algorithms, it is clearly not the best because it has no practical use for small value multiplications. what you are using it for defines which is best
you are still noob

>> No.1108912

Dumbasses
I can solve anything in my head

>> No.1108919

>>1108910
actually, it does work fairly well even for comparably small numbers. It's clearly not as fast as the algorithm you gave, but it's not absurdly slow either. For details on how such an algorithm can be constructed see the first couple chapters of this book, where I read about the same topic:
http://www.springerlink.com/content/rp6j7455u08761l7/

>> No.1108925

http://en.wikipedia.org/wiki/Multiplication_algorithm
enjoy

>> No.1108956

why don't you retards use longs to multiply then. effin faggots

>> No.1108974

>>1108956

....which is still a data type with limited storage.....

>> No.1108987

ITT
Noobs noobing noobs

>> No.1109781

Fürer's algorithm

>> No.1111656

>>1108956
> implying longs won't overflow