4 ms·

One nice thing from knowing squares is that you can calculate for example 23 * 47 as (35 - 12) * (35 + 12) = 35^2 - 12^2. But this doesn't always work and you

One nice thing from knowing squares is that you can calculate for example 23 * 47 as (35 - 12) * (35 + 12) = 35^2 - 12^2. But this doesn't always work and you still need to be good at adding/subtracting.

amelius 2y ago
What is wrong with computing it just as 7*23 + 40*23 ?
- bibanez 2y ago
  Nothing, but if you know perfect squares you will do 3 additions/subtractions instead of 2 products and 1 addition
JadeNB 2y ago
> But this doesn't always work and you still need to be good at adding/subtracting. It does always work. If you mean that not every integer product can be written this way, you're right; 23 × 46 can't, unless you're willing to memorise squares of half-integers. But, if avoiding non-squaring multiplication is really key, then you can still just write 23 × 46 = 23 × 47 - 23, and then compute 23 × 47 = 35^2 - 15^2 as you suggest.
- shiandow 2y ago
  Or you could do ((46+23)^2 -(46-23)^2) / 4 Or one of several similar formulae, but each has its own pros and cons.
  - JadeNB 2y ago
    > Or you could do ((46+23)^2 -(46-23)^2) / 4 Sure, of course that works algebraically, though this method will always involve at least one bigger square, and division by 4, which, if working in base 10, can be implemented with exactly the computational complexity of multiplying by 25—so perhaps is also meant to be avoided, if we're trying to avoid multiplication! As you say, there are pros and cons of all approaches, including just doing the multiplication.
    - shiandow 2y ago
      I mean the initial method is just ((46+23)/2)^2 - ((46-23)/2)^2 so you kind of need to be good at halving to use that method in the first place.
kstrauser 2y ago
I'm good at arithmetic, to the point that my buddy called from across the country a few days ago to have me perform "hard" math questions for his kids. It's always a relief when they pick random numbers like "what's 83 times 97?" Whew. Well, 90**2 - 7**2 = 8051. As a bonus, when you explain that method, it sounds even more impressive to them: "you mean, you just know what 63 squared is?" Sure, but it didn't happen overnight.
- bee_rider 2y ago
  I think your star star just rendered as a star.
  - kstrauser 2y ago
    Oops, good catch.
- teachrdan 2y ago
  That close to 100, I'll just do 83*100 - 83*3
  - kstrauser 2y ago
    That takes me longer for whatever reason. It would also require me to identify that as a special "close to 100" case I'd have already calculated it the other way by the time decided to swap in that algorithm. Basically, branching takes me too many cycles.
nine_k 2y ago
Hmm, this looks like a neat trick to make hardware multiplication faster. Say, for 8-bit numbers it would require 3 8-bit additions/subtractions and one 16-bit addition, one 9-bit shift, and two lookups in a 512-byte table of squares, and zero conditional processing, as opposed to 8 16-bit additione, 8 16-bit shifts, and 8 LSB tests that a naive iterative algorithm would do. I wonder what real integer multiplication hardware uses.
- amelius 2y ago
  It all depends on how you can parallellize it.

amelius 2y ago

What is wrong with computing it just as 7*23 + 40*23 ?

bibanez 2y ago
Nothing, but if you know perfect squares you will do 3 additions/subtractions instead of 2 products and 1 addition

JadeNB 2y ago

> But this doesn't always work and you still need to be good at adding/subtracting. It does always work. If you mean that not every integer product can be written this way, you're right; 23 × 46 can't, unless you're willing to memorise squares of half-integers. But, if avoiding non-squaring multiplication is really key, then you can still just write 23 × 46 = 23 × 47 - 23, and then compute 23 × 47 = 35^2 - 15^2 as you suggest.

shiandow 2y ago
Or you could do ((46+23)^2 -(46-23)^2) / 4 Or one of several similar formulae, but each has its own pros and cons.
- JadeNB 2y ago
  > Or you could do ((46+23)^2 -(46-23)^2) / 4 Sure, of course that works algebraically, though this method will always involve at least one bigger square, and division by 4, which, if working in base 10, can be implemented with exactly the computational complexity of multiplying by 25—so perhaps is also meant to be avoided, if we're trying to avoid multiplication! As you say, there are pros and cons of all approaches, including just doing the multiplication.
  - shiandow 2y ago
    I mean the initial method is just ((46+23)/2)^2 - ((46-23)/2)^2 so you kind of need to be good at halving to use that method in the first place.

kstrauser 2y ago

I'm good at arithmetic, to the point that my buddy called from across the country a few days ago to have me perform "hard" math questions for his kids. It's always a relief when they pick random numbers like "what's 83 times 97?" Whew. Well, 90**2 - 7**2 = 8051. As a bonus, when you explain that method, it sounds even more impressive to them: "you mean, you just know what 63 squared is?" Sure, but it didn't happen overnight.

bee_rider 2y ago
I think your star star just rendered as a star.
- kstrauser 2y ago
  Oops, good catch.
teachrdan 2y ago
That close to 100, I'll just do 83*100 - 83*3
- kstrauser 2y ago
  That takes me longer for whatever reason. It would also require me to identify that as a special "close to 100" case I'd have already calculated it the other way by the time decided to swap in that algorithm. Basically, branching takes me too many cycles.

nine_k 2y ago

Hmm, this looks like a neat trick to make hardware multiplication faster. Say, for 8-bit numbers it would require 3 8-bit additions/subtractions and one 16-bit addition, one 9-bit shift, and two lookups in a 512-byte table of squares, and zero conditional processing, as opposed to 8 16-bit additione, 8 16-bit shifts, and 8 LSB tests that a naive iterative algorithm would do. I wonder what real integer multiplication hardware uses.

amelius 2y ago
It all depends on how you can parallellize it.