Tag Archives: arithmetic

A multiplication algorithm found in a book by Paul Erdős: how does it work?

From stackoverflow

# -*- coding: utf-8 -*-
"""
Created on Mon Mar 20 09:08:06 2017

@author:
From Erdős and Surányi's Topics in the theory of numbers (Springer),
chapter 1 ("Divisibility, the Fundamental Theorem of Number Theory"):

We can multiply two (positive integer) numbers together
in the following way:
1. Write the two numbers down next to each other.
2. Divide the first in half, rounding down to an integer,
and write the result below it.
3. Double the second number, writing the result below it.
4. Continue this halving / doubling until we are left
with 1 in the first column.
5. Cross out all those numbers in the second column
that are opposite an even number and add the remaining
numbers in this column together to get the product.

Prove that this works.

This method is often called "Russian peasant multiplication".

It's often justified by thinking about writing the first number in binary.
Here's another way to explain it:
    At each step, we're replacing a pair (p,q) either by (p2, 2q)
    (when p is even) or by (p−1/2, 2q) (when p is odd).

    In the first case, when p is even, the product of the two numbers
    doesn't change: p⋅q=p/2 2p⋅.

    In the second case, when p is odd, p−1/2⋅2q=p⋅q−q.
    So the product has decreased by q, and we should set q aside for later.

    Eventually, we get to a pair (1,r) whose product is easy to compute:
        it's just r.
    Because we've kept track of how the product of a pair has changed,
    we know that the original product is equal to this product,
    plus all the numbers we've set aside. But we set aside q from the pair
    (p,q) whenever p is odd. So adding the numbers we set aside to the
    final number just corresponds to adding up the second number in every
    pair whose first number is odd.

The ancient Egyptains had a similar precursor method:
    en.wikipedia.org/wiki/Ancient_Egyptian_multiplication
    – Henno Brandsma Mar 17 at 4:55

Note this method can be adapted for other number bases,
there is nothing special about 2, except for the fact that it is
immediate to calculate mod 2 of a base 10 representation.
To adapt it for base b, divide by b in each step and record the
remainder, later multiply each reminder by the right column and add.
Also, stop the first column when reaching a number less than b.
The right column is generated by multiplying by b.

And this is an example, 73⋅217:
(73,217)(36,434)(18,868)(9,1736)(4,3472)(2,6944)(1,13888)
Then 73⋅217=217+1736+13888=15841, which is correct.
"""

def russian_peasant_multiplication(p, q, acc=0):
    '''
    Returns de product of a and b if acc == 0
    using recursive conversion of the first factor to binary
    '''
    print(p, q, acc + q)
    if p == 1:
        return acc + q
    elif (p % 2) == 0:
        return russian_peasant_multiplication(p // 2, q * 2, acc)
    else:
        return russian_peasant_multiplication(p // 2, q * 2, acc + q)

assert russian_peasant_multiplication(73, 217) == 15841

Advertisements

what went wrong? units

Translation of the allegory designed by the Ikhwān al-Ṣafā’ to explain the calculation of the Great Year.

Know further, my brother, that the wise men of India have formulated an allegory of the revolutions of these stars around the Earth, so that the comprehension of this may be brought closer to those who learn and that its representation may be made easier to those who meditate. According to their report, a king among kings built a city with a circumference of 60 parasangs and sent seven individuals to revolve around it at different paces: one of them 1 parasang every day, another one 2 parasangs every day, the third 3 parasangs every day, the
fourth 4 parasangs every day, the fifth 5 parasangs every day, the sixth 6 parasangs every day, and the seventh, 7 parasangs every day. And the king told them: ‘Revolve around this city, starting from this door; when, by the number of your revolutions, you join together at the same door, come [to me] and announce to me how many revolutions each one you will have completed’. Whoever has understood the computation of the revolutions of these individuals around the city and succeeded to figure it by imagination is likely to understand the revolutions of these stars around the Earth, and to figure out how many revolutions it will take them to join together in the first [minute] of Aries, in the same way as they were when they started.
As for the computation [concerning] these individuals, it is as follows. After 60 days, 6 individuals join together at the door of the city. The first one has completed 1 revolution, the second 2 revolutions, the third 3 revolutions, the fourth 4 revolutions, the fifth 5 revolutions, the sixth 6 revolutions. As for the one who completes, every day, 7 [parasangs], he has completed 8 revolutions plus 4/7 of the parasangs of a revolution, so that these individuals must renew the revolution. After 120 days, they join together once again at the door
and each one has completed his first count once again, but the seventh has completed 17 revolutions plus 1/7 of the parasangs [of a revolution], so that they must renew the revolution. After 180 days, the six join together for the third time and each one has completed, for the third time, his first count, but the seventh companion has completed 25 revolutions plus 5/7, so that they must renew the revolution. After 240 days, they join together for the fourth time and each one of them has completed his first count, but the seventh companion has completed 34 revolutions plus 2/7, so that they must renew the revolution. After 300 days, they join
together for the fifth time, but the seventh companion has completed 42 revolutions plus 6/7, so that they must renew the revolution. After 360 days, they join together for the sixth time and each one of them has completed his first count for the sixth time, but the seventh companion has completed 51 revolutions plus 3/7 of the parasangs [of the revolution], so that they must renew the revolution. After 420 days, all of them join together at the door of the city: the first one has completed 7 revolutions, the second 14 revolutions, the third 21 revolutions, the fourth 28 revolutions, the fifth 35 revolutions, the sixth 42 revolutions, and the seventh has completed 60 revolutions. This is the allegory that the wise men of India have invented in order to account for the revolutions of the spheres and the stars around the Earth. Thus, the Earth is like this city that was built with a circumference of 60 parasangs. The seven planets and their revolutions around the Earth are like these seven individuals. The difference in speed and slowness between their movements are like the differences between the courses of these individuals. As for the king, he is the God, the Creator, the Founder – Blessed be the God, Lord of the Worlds.

Exponential growth

 Big changes await us. An unrecognizable economy. The main lesson for me is that growth is not a “good quantum number,” as physicists will say: it’s not an invariant of our world. Cling to it at your own peril.

Note: This conversation is my contribution to a series at www.growthbusters.org honoring the 40th anniversary of the Limits to Growth study. You can explore the series here. Also see my previous reflection on the Limits to Growth work. You may also be interested in checking out and signing the Pledge to Think Small and consider organizing an Earth Day weekend house party screening of the GrowthBusters movie.

Published on Sep 19, 2012
This video quickly covers the key points that you will find in the long version. Everyone needs to see the long version but many won’t because they don’t have the time. My hope is that people will watch this short version and then be motivated to watch the long version.

I came across “The Most Important Video You’ll Ever See” on YouTube and clicked on it. I didn’t realize that it was an eight part video that lasted over an hour but after finishing part one I had no choice but to watch the whole thing. It truly could be called the most important video you’ll ever see.

Continue reading

A program to generate “factorization diagrams”.

The Math Less Traveled

In an idle moment a while ago I wrote a program to generate "factorization diagrams". Here’s 700:

It’s easy to see (I hope), just by looking at the arrangement of dots, that there are $latex 7 \times 5 \times 5 \times 2 \times 2$ in total.

Here’s how I did it. First, a few imports: a function to do factorization of integers, and a library to draw pictures (yes, this is the library I wrote myself; I promise to write more about it soon!).

>moduleFactorizationwhere>>importMath.NumberTheory.Primes.Factorisation(factorise)>>importDiagrams.Prelude>importDiagrams.Backend.Cairo.CmdLine>>typePicture=DiagramCairoR2

The primeLayout function takes an integer n (assumed to be a prime number) and some sort of picture, and symmetrically arranges n copies of the picture.

View original post 583 more words

What does it mean to give 100%?

What equals 100% in life? Here’s a little mathematical formulation that might
help answer these questions.

If
A B C D E F G H I J K L M N O P Q R S
T U V W X Y Z
is represented as
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17
18 19 20 21 22 23 24 25 26.
then

H-A-R-D-W-O-R-K
8+1+18+4+23+15+18+11 = 98%

and

K-N-O-W-L-E-D-G-E
11+14+15+23+12+5+4+7+5 = 96%

But
A-T-T-I-T-U-D-E
1+20+20+9+20+21+4+5 = 100%

Therefore, one can conclude with mathematical certainty that:

While Hard Work and Knowledge will get you close, Attitude will
get you there!

However, consider

B-U-L-L-S-H-I-T
2+21+12+12+19+8+9+20 = 103%

So, Hard Work and Knowledge will get you close, Attitude will get you there and Bullshit will take you over the top! And look how far
A-S-S K-I-S-S-I-N-G
will take you:

1+19+19+11+9+19+19+9+14+7 = 118%

So the next time someone asks you to give more than 100%, you know what’s required of you!

http://en.wikipedia.org/wiki/Numerology

La aritmética de Trachtenberg

Así como Viktor Emil Frankl desarrollo la logoterapia para superar los rigores de los campos de concentración Nazi, Jakow Trachtenberg ocupo su mente en desarrollar un sistema de aritmética mental al verse en la misma situación.

El sistema Trachtenberg de rápido cálculo mental, similar a las matemáticas Védicas, consiste en un conjunto de patrones para realizar operaciones aritméticas. Los algoritmos más importantes son multiplicación,división, y adición. El método también incluye algoritmos especializados para realizar multiplicaciones por números entre 5 y 13.

Multiplicación por 11

Abusando de la notación

(11)a = 11Σai10i =

an10n+1 + [Σj=0n-1(aj+aj+1)10j ]+ a0

Multiplicación por 12

(12)a = 12Σai10i =

an10n+1 + [Σj=0n-1 (aj+2aj+1)10j ]+ 2a0

Multiplicación por 6

Definiendo

bj = aj/2, donde / denota división entera

cj = aj mod 2

tenemos

aj = 2bj + cj

(6)a = (10/2)Σai10i + Σai10i =

Σbi10i+1 + Σ(ai + 5ci)10i

bn10n+1 + [Σj=1n(aj + 5cj + bj-1)10j ]+ (a0 + 5c0)

Expresando el algoritmo en python:

def x6(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(digit + odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result

Multiplicación por 7

De manera similar al caso anterior:

aj = 2bj + cj

(7)a = (10/2)Σai10i + Σ2ai10i =

Σbi10i+1 + Σ(2ai + 5ci)10i

bn10n+1 + [Σj=1n(2aj + 5cj + bj-1)10j ]+ (a0 + 5c0)

Expresando el algoritmo en python:

def x7(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(2*digit + odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result

Multiplicación por 5

De manera similar al caso anterior:

aj = 2bj + cj

(5)a = (10/2)Σai10i =

Σbi10i+1 + Σ(5ci)10i

bn 10n+1 + [Σj=1n(5cj + bj-1)10j ]+ (5c0)

Expresando el algoritmo en python:

def x5(number):
previous = 0
result = 0
power_of_10 = 1
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result =
(odd_term + previous ) *
power_of_10 + result
previous = digit//2
power_of_10 *= 10
number = number // 10
result = previous * power_of_10 + result
return result

Multiplicación por 9

Definiendo

b = 10n+1 – Σj=0naj , o sea el complemento a 10 de a

tenemos

(9)a = 10a –a =

10a –a + b – b =

10a + b – 10n+1 =

(an – 1)10n+1 + [Σj=1n(bj + aj-1)10j ]+ (b0 )

Expresando el algoritmo en python:

def x9(number):
previous = number%10
result = 10 - previous
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
result =
(9 - digit + previous ) *
power_of_10 + result
previous = digit
power_of_10 *= 10
number = number // 10
result =
(previous-1) * power_of_10 +
result
return result

Multiplicación por 8

Definiendo

b = 10n+1 – Σj=0naj , o sea el complemento a 10 de a

tenemos

(8)a = 10a –2a =

10a –2a +2 b – 2b =

10a + 2b – (2)10n+1 =

(an – 2)10n+1 + [Σj=1n(2bj + aj-1)10j ]+ (2b0 )

Expresando el algoritmo en python:

def x8(number):
previous = number%10
result = 2*(10 - previous)
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
result =
(2*(9 - digit) + previous ) *
power_of_10 + result
previous = digit
power_of_10 *= 10
number = number // 10
result =
(previous-2) *
power_of_10 + result
return result

Multiplicación por 3 y por 4

Los algoritmos para multiplicar por 3 y por 4 combinan las ideas usadas en la multiplicación por 5 y por 9.

Definiendo

b = 10n+1 – Σj=0naj , o sea el complemento a 10 de a

ai = 2ci + di, donde

ci = ai/2

di = ai mod 2

tenemos

(4)a = 5a –a =

10c + 5d + b – 10n+1

(3)a = 5a –2a =

10c + + 5d + 2b – (2)10n+1

Expresando los algoritmos en python:

def x3(number):
digit = number%10
result = 2*(10 - digit)
if digit % 2:
result += 5
previous = digit // 2
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result +=(2*(9 - digit) + odd_term + previous ) * power_of_10
previous = digit//2
power_of_10 *= 10
number = number // 10
result = (previous-2) * power_of_10 + result
return result

def x4(number):
digit = number%10
result = (10 - digit)
if digit % 2:
result += 5
previous = digit // 2
power_of_10 = 10
number = number // 10
while (number):
digit = number%10
odd_term = 5 if digit%2 else 0
result +=((9 - digit) + odd_term + previous ) * power_of_10
previous = digit//2
power_of_10 *= 10
number = number // 10
result = (previous-1) * power_of_10 + result
return result

Referencias