The New Sudoku Players' Forum

[StrmCkr]

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

[Leren]

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

[dobrichev]

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

[StrmCkr]

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..

[999_Springs]

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?

[StrmCkr]

That works too. Abilet large byte size used per addition.

[Mathimagics]

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)

[dobrichev]

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.

[Leren]

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

[rjamil]

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

[Smythe Dakota]

How about just doing multiplication the way rabbits do it?

Bill Smythe