But did the Egyptians and Chinese really use binary? I don't know of what he says but neither used zeros and this doubling proportions math adds what's there with no need for what's not, and doubling is easy.
Looked over the second trick in that video and got it.
You multiply two numbers by halving (right-shift) one and doubling (left-shift) the other and add the doubled column value to an accumulator when the halved column value is odd (& 1 == 1).
13 x 24 -- 13 is odd, total = 24 bit3 1
6 x 48 -- 6 is even, don't add bit2 0
3 x 96 -- 3 is odd, total += 96 bit1 1
1 x 192 1 is odd, total += 192 bit0 1
total = 312
1011 is binary 13 decimal, it's a high to low bit version of the first method shown, still only adds proportions for bits that add to 13. There is no 48 to add in 312 as there is no 4 in 0b1011, the low bit is 0.
I wonder how it compares with the multiply we have now? Must take a crack at that one and find a similar divide!
PS - I like how this one starts right at one value, is there a quick way to pick the operand with the least bits set to cut the number of adds? Maybe always halve the smaller value to cut steps!
13 x 25
13 x 100 = 1300
13 X 50 = 650
13 x 25 = 325
so
13 x 24 = 325 -13 = 312
Sorry, its 9:30am Sat morning and first coffee of the day has soaked in?
Don't ask me why 25 type solutions, keep popping into my head like that.
Could it be having to do it by mentally and by hand in High School, we had slide rules and the only electronic hand held calculator was owned by our Applied Maths teacher, a simple scientific Canon model, not sure what it cost, but must have been a pretty penny.
GoForSmoke:
13 x 24 -- 13 is odd, total = 24 bit3 1
6 x 48 -- 6 is even, don't add bit2 0
3 x 96 -- 3 is odd, total += 96 bit1 1
1 x 192 1 is odd, total += 192 bit0 1
total = 312
Slower than Arduino multiply for 32 bit values. MUCH slower.
#include "Arduino.h"
long bmult32( long smaller, long bigger ) // product must fit in long
{
long total = 0;
while( smaller > 0 )
{
if ( smaller & 1 )
{
total += bigger;
}
smaller >>= 1;
bigger <<= 1;
}
return total;
}
long product;
long bproduct;
long paritycount;
long over16count;
unsigned long startUsec;
unsigned long endUsec;
unsigned long elapsedUsec;
void setup()
{
Serial.begin( 115200 ); // if you can run faster with your IDE then do!
Serial.println( F( "\n\nStartup!\n" ));
Serial.print( F( "23 x 57 = " ));
product = bmult32( 23, 57 );
Serial.println( product );
Serial.print( F( "633 x 15767 = " ));
product = bmult32( 633, 15767 );
Serial.println( product );
Serial.print( F( "2100 x 17500 = " ));
product = bmult32( 2100, 17500 );
Serial.println( product );
startUsec = micros();
for ( long x = 2; x < 2000L; x++ )
{
for ( long y = x + 1; y < 3000L; y++ )
{
product = x * y;
if ( product & 1 )
{
paritycount++;
}
if ( product > 0xFF )
{
over16count;
}
}
}
endUsec = micros();
elapsedUsec = endUsec - startUsec;
Serial.print( F( "\ntime in micros = " ));
Serial.println( elapsedUsec );
Serial.print( F( "odd parity count = " ));
Serial.println( paritycount );
Serial.print( F( "over 16 bit count = " ));
Serial.println( over16count );
paritycount = over16count = 0;
startUsec = micros();
for ( long x = 2; x < 2000L; x++ )
{
for ( long y = x + 1; y < 3000L; y++ )
{
bproduct = bmult32( x, y );
if ( bproduct & 1 )
{
paritycount++;
}
if ( product > 0xFF )
{
over16count;
}
}
}
endUsec = micros();
elapsedUsec = endUsec - startUsec;
Serial.print( F( "\ntime in micros = " ));
Serial.println( elapsedUsec );
Serial.print( F( "odd parity count = " ));
Serial.println( paritycount );
Serial.print( F( "over 16 bit count = " ));
Serial.println( over16count );
Serial.println( );
for ( long x = 2; x < 2000; x++ )
{
for ( long y = x + 1; y < 3000; y++ )
{
product = x * y;
bproduct = bmult32( x, y );
if ( product != bproduct )
{
Serial.print( x);
Serial.print( F( " x " ));
Serial.print( y );
Serial.print( F( " ? " ));
Serial.println( product );
Serial.print( F( " != " ));
Serial.println( bproduct );
}
}
}
}
void loop()
{
}
AFAIK Babylonians grouped numbers by 5s and 10s like the Romans, and used a base-60 system. From whence there are 60 seconds in a minute, and 360 degrees in a circle's arc.