## Reducing mutiplicative steps

Anything goes, but keep it seemly...

### Reducing mutiplicative steps

1467 * 2531 = 3712977

Requires 16 single mutiplicative steps

Karatsuba’s method reduces this to 9 single mutiplicative steps

My method ive used for years taught to me by my father for adding stacks of random numbers together quickly modified by me to do high powered multiplication.

Start by rounding each number to the nearest whole number and remember that number

1467 + 533 = 2,000
2531 + 469 =3,000

2k x 3k = 6m (or viewed as 3k +3k x 1k)

Step 2:
realize that we have a larger number and remove the offset diffrence by both sides inflation rates
533 x 3k (1599k) (viewed as 533 + its self 3 times)
469 x 2k ( 938k) (viewed as 469 + its self twice)

Step 3 :
Relise that step 2 over offsets and add that of set back on
533x469 = 249977

Repeat steps 1 - 3 on step 3. For each mutipler part thats not a power of 10.
For this example:
(469+31)*(533+67) - (31*600) - (67*500) + (67*31)

(67 +3) * (31*9) - (9*40) - (3*70) + (9*3)

Results in no multiplication like this .
3m+3m - (533k +533 k +533k) - (469k + 469k) +(60k+60k+60k+60k+60k) - (3100+3100+3100+3100+3100+3100) ( 6700+6700+6700+6700+6700) +( 700+700+700+700) - (90+90+90+90) - (70+70+70) + (9+9+9)

6m - 2537k + 249977 = 3,712,977
Last edited by StrmCkr on Thu Jan 09, 2020 10:35 pm, edited 2 times in total.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Re: Reducing mutiplicative steps

Even faster, for very large numbers, is the Schönhage–Strassen algorithm, which you can read all about here.

Leren
Leren

Posts: 4013
Joined: 03 June 2012

### Re: Reducing mutiplicative steps

My secret method resolves the above with 1467 additions and no multiplication.
dobrichev
2016 Supporter

Posts: 1794
Joined: 24 May 2010

### Re: Reducing mutiplicative steps

Apprently there is a new one that beats Strauss publisbed this year for 0(n log n) time.
Joris van der Hoeven

Re: Reducing mutiplicative steps

Postby dobrichev » 09 Jan 2020 14:51
My secret method resolves the above with 1467 additions and no multiplication.

Funny guy 2531 added to its self 1467 times

....
Mine listed does it in 36.additions and 1 subtraction NO mutiplication..
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Re: Reducing mutiplicative steps

well then why can't you just do

1467000 + 1467000 + 146700 + 146700 + 146700 + 146700 + 146700 + 14670 + 14670 + 14670 + 1467

that's 10 additions. putting zeros on the end hardly counts as a multiplication does it?
999_Springs

Posts: 531
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

### Re: Reducing mutiplicative steps

That works too. Abilet large byte size used per addition.
Some do, some teach, the rest look it up.

StrmCkr

Posts: 1205
Joined: 05 September 2006

### Re: Reducing mutiplicative steps

dobrichev wrote:My secret method resolves the above with 1467 additions and no multiplication.

Surely no more than 22 additions are needed? (1467 has 11 significant bits)

Mathimagics
2017 Supporter

Posts: 1614
Joined: 27 May 2015
Location: Canberra

### Re: Reducing mutiplicative steps

Switching to binary representation is arbitrary choice.
I would switch to base-1467 representation and replace the multiplication by the easiest operation -- increment..
edit: increment is wrong of course. 1467(base 10) transforms to 1(base 1467) and the result in base 1467 is 2531(base 10) transformed to base 1467.
Last edited by dobrichev on Sat Jan 11, 2020 11:12 am, edited 1 time in total.
dobrichev
2016 Supporter

Posts: 1794
Joined: 24 May 2010

### Re: Reducing mutiplicative steps

Considering the above posts I have a secret method which uses 1 multiplication and 0 additions Leren
Leren

Posts: 4013
Joined: 03 June 2012

### Re: Reducing mutiplicative steps

Code: Select all
`    1   4   6   7  |---|---|---|---|  |0 /|0 /|1 /|1 /|  | / | / | / | / | 2  |/ 2|/ 8|/ 2|/ 4|  |---|---|---|---|  |0 /|2 /|3 /|3 /|  | / | / | / | / | 5  |/ 5|/ 0|/ 0|/ 5|  |---|---|---|---|  |0 /|1 /|1 /|2 /|  | / | / | / | / | 3  |/ 3|/ 2|/ 8|/ 1|  |---|---|---|---|  |0 /|0 /|0 /|0 /|  | / | / | / | / | 1  |/ 1|/ 4|/ 6|/ 7|  |---|---|---|---|        Step 1    1   4   6   7  |---|---|---|---|  |0 /|0 /|1 /|1 /|  | / | / | / | / | 20 |/ 2|/ 8|/ 2|/ 4|  |---|---|---|---|  |0 /|2 /|3 /|3 /|  |1/ | / | / | / | 53 |/ 5|/ 0|/ 0|/ 5|  |---|---|---|---|  |0 /|1 /|1 /|2 /|  |1/ | / | / | / | 37 |/ 3|/ 2|/ 8|/ 1|  |---|---|---|---|  |0 /|0 /|0 /|0 /|  |1/ |1/ | / | / | 11 |/ 1|/ 4|/ 6|/ 7|  |---|---|---|---|   2   9   7   7        Step 2`

R. Jamil
rjamil

Posts: 604
Joined: 15 October 2014
Location: Karachi, Pakistan

### Re: Reducing mutiplicative steps

How about just doing multiplication the way rabbits do it?

Bill Smythe
Smythe Dakota

Posts: 564
Joined: 11 February 2006