Reducing mutiplicative steps

Anything goes, but keep it seemly...

Reducing mutiplicative steps

Postby StrmCkr » Thu Jan 09, 2020 7:15 pm

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)
Add these together = 2537k

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.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: Reducing mutiplicative steps

Postby Leren » Thu Jan 09, 2020 8:38 pm

You can read all about the Karatsuba algorithm here.

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

Leren
Leren
 
Posts: 5124
Joined: 03 June 2012

Re: Reducing mutiplicative steps

Postby dobrichev » Thu Jan 09, 2020 8:51 pm

My secret method resolves the above with 1467 additions and no multiplication.
dobrichev
2016 Supporter
 
Posts: 1863
Joined: 24 May 2010

Re: Reducing mutiplicative steps

Postby StrmCkr » Thu Jan 09, 2020 10:05 pm

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.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: Reducing mutiplicative steps

Postby 999_Springs » Thu Jan 09, 2020 11:10 pm

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: 591
Joined: 27 January 2007
Location: In the toilet, flushing down springs, one by one.

Re: Reducing mutiplicative steps

Postby StrmCkr » Fri Jan 10, 2020 1:20 am

That works too. Abilet large byte size used per addition.
Some do, some teach, the rest look it up.
stormdoku
User avatar
StrmCkr
 
Posts: 1433
Joined: 05 September 2006

Re: Reducing mutiplicative steps

Postby Mathimagics » Fri Jan 10, 2020 2:07 pm

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)
User avatar
Mathimagics
2017 Supporter
 
Posts: 1926
Joined: 27 May 2015
Location: Canberra

Re: Reducing mutiplicative steps

Postby dobrichev » Sat Jan 11, 2020 8:35 am

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: 1863
Joined: 24 May 2010

Re: Reducing mutiplicative steps

Postby Leren » Sat Jan 11, 2020 8:35 am

Considering the above posts I have a secret method which uses 1 multiplication and 0 additions :D Leren
Leren
 
Posts: 5124
Joined: 03 June 2012

Re: Reducing mutiplicative steps

Postby rjamil » Sat Jan 11, 2020 1:41 pm

How about Lattice multiplication method?

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 /|
  | / | / | / | / | 2
0 |/ 2|/ 8|/ 2|/ 4|
  |---|---|---|---|
  |0 /|2 /|3 /|3 /|
  |1/ | / | / | / | 5
3 |/ 5|/ 0|/ 0|/ 5|
  |---|---|---|---|
  |0 /|1 /|1 /|2 /|
  |1/ | / | / | / | 3
7 |/ 3|/ 2|/ 8|/ 1|
  |---|---|---|---|
  |0 /|0 /|0 /|0 /|
  |1/ |1/ | / | / | 1
1 |/ 1|/ 4|/ 6|/ 7|
  |---|---|---|---|
   2   9   7   7
        Step 2

4x4 multiplications and 4+4 additions.

R. Jamil
rjamil
 
Posts: 785
Joined: 15 October 2014
Location: Karachi, Pakistan

Re: Reducing mutiplicative steps

Postby Smythe Dakota » Sun Jan 12, 2020 1:56 pm

How about just doing multiplication the way rabbits do it?

Bill Smythe
Smythe Dakota
 
Posts: 564
Joined: 11 February 2006


Return to Coffee bar