Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #15050 > unrolled thread

Russian Peasant Multiplication / was question on how to do this

Started byRichard Fateman <fateman@cs.berkeley.edu>
First post2013-06-29 08:47 +0000
Last post2013-07-03 08:53 +0000
Articles 7 — 4 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  Russian Peasant Multiplication / was question on how to do this Richard Fateman <fateman@cs.berkeley.edu> - 2013-06-29 08:47 +0000
    Re: Russian Peasant Multiplication / was question on how to do this d.a.paxton@gmail.com - 2013-06-30 07:26 +0000
    Re: Russian Peasant Multiplication / was question on Bob Hanlon <hanlonr357@gmail.com> - 2013-07-01 09:45 +0000
    Re: Russian Peasant Multiplication / was question on how to do this d.a.paxton@gmail.com - 2013-07-02 04:35 +0000
    Re: Russian Peasant Multiplication / was question on James Stein <mathgroup@stein.org> - 2013-07-03 08:47 +0000
    Re: Russian Peasant Multiplication / was question on how to do this d.a.paxton@gmail.com - 2013-07-03 08:50 +0000
    Re: Russian Peasant Multiplication / was question on Bob Hanlon <hanlonr357@gmail.com> - 2013-07-03 08:53 +0000

#15050 — Russian Peasant Multiplication / was question on how to do this

FromRichard Fateman <fateman@cs.berkeley.edu>
Date2013-06-29 08:47 +0000
SubjectRussian Peasant Multiplication / was question on how to do this
Message-ID<kqm6u7$hp5$1@smc.vnet.net>
Dave --
1.  You should try to come up with a useful subject line
in the future.
2. It is called Russian Peasant Multiplication (which you may
find on Google).
3. There is no reason to believe that a procedural algorithm
has a formula, but in this case I think the inverse is known
as division :)

[toc] | [next] | [standalone]


#15057

Fromd.a.paxton@gmail.com
Date2013-06-30 07:26 +0000
Message-ID<kqomjq$p79$1@smc.vnet.net>
In reply to#15050
On Saturday, June 29, 2013 2:47:03 AM UTC-6, Richard Fateman wrote:
> Dave --
>
> 1.  You should try to come up with a useful subject line
>
> in the future.
>
> 2. It is called Russian Peasant Multiplication (which you may
>
> find on Google).
>
> 3. There is no reason to believe that a procedural algorithm
>
> has a formula, but in this case I think the inverse is known
>
> as division :)

I am sorry for posting a question that is improper.  It is a matter of rounding as a floor or ceiling question I guess wondering nomenclature.  If the lowest count on the numbers in a multiply are let's say 7 and 5.  We multiple these and get 35.  How does on drop the 5 into the lowest of the answer and carry the 3?  Since 7 and 5 and also 35 are know known we do this..  In base ten we multiply by ten.  Divide out the seven and get fifty.  Divide that by ten and get the 5 drop out number.  Then put the the thirty five minus the drop out number and then divide by ten again.  Gives three.  The carry number.  So I guess in using this for any base number system we do have a divide as an inverse function for any variables in the course of a multiply.

[toc] | [prev] | [next] | [standalone]


#15076 — Re: Russian Peasant Multiplication / was question on

FromBob Hanlon <hanlonr357@gmail.com>
Date2013-07-01 09:45 +0000
SubjectRe: Russian Peasant Multiplication / was question on
Message-ID<kqrj3p$4bl$1@smc.vnet.net>
In reply to#15050
Clear[russianPeasantMultiply];


russianPeasantMultiply[
   x_Integer, y_Integer] :=
  Sign[x]*Sign[y]*
   Total[
    Cases[
      NestWhileList[
       Floor[{1/2, 2}*#] &,
       Sort[Abs[{x, y}]],
       (First[#] > 1) &],
      {_?OddQ, _}][[All, -1]]];


m = 10^6;
x = RandomInteger[{-m, m}];
y = RandomInteger[{-m, m}];


russianPeasantMultiply[x, y] == x*y

True



Bob Hanlon


On Sun, Jun 30, 2013 at 3:29 AM, <d.a.paxton@gmail.com> wrote:

> On Saturday, June 29, 2013 2:47:03 AM UTC-6, Richard Fateman wrote:
> > Dave --
> >
> > 1.  You should try to come up with a useful subject line
> >
> > in the future.
> >
> > 2. It is called Russian Peasant Multiplication (which you may
> >
> > find on Google).
> >
> > 3. There is no reason to believe that a procedural algorithm
> >
> > has a formula, but in this case I think the inverse is known
> >
> > as division :)
>
> I am sorry for posting a question that is improper.  It is a matter of
> rounding as a floor or ceiling question I guess wondering nomenclature.  If
> the lowest count on the numbers in a multiply are let's say 7 and 5.  We
> multiple these and get 35.  How does on drop the 5 into the lowest of the
> answer and carry the 3?  Since 7 and 5 and also 35 are know known we do
> this..  In base ten we multiply by ten.  Divide out the seven and get
> fifty.  Divide that by ten and get the 5 drop out number.  Then put the the
> thirty five minus the drop out number and then divide by ten again.  Gives
> three.  The carry number.  So I guess in using this for any base number
> system we do have a divide as an inverse function for any variables in the
> course of a multiply.
>
>

[toc] | [prev] | [next] | [standalone]


#15090

Fromd.a.paxton@gmail.com
Date2013-07-02 04:35 +0000
Message-ID<kqtl9u$atp$1@smc.vnet.net>
In reply to#15050
On Saturday, June 29, 2013 2:47:03 AM UTC-6, Richard Fateman wrote:
> Dave --
>
> 1.  You should try to come up with a useful subject line
>
> in the future.
>
> 2. It is called Russian Peasant Multiplication (which you may
>
> find on Google).
>
> 3. There is no reason to believe that a procedural algorithm
>
> has a formula, but in this case I think the inverse is known
>
> as division :)

Bob,  Thanks on that.  I see the use of the floor function.  This whole idea is trivial when one can use that.  What I am trying to do is basically do the floor function as a linear equation.  This is useful for pulling numbers apart.  Like a number 13.  How does one algebraically make it 1 and 3 or 10 and 3.  Either.

[toc] | [prev] | [next] | [standalone]


#15095 — Re: Russian Peasant Multiplication / was question on

FromJames Stein <mathgroup@stein.org>
Date2013-07-03 08:47 +0000
SubjectRe: Russian Peasant Multiplication / was question on
Message-ID<kr0oe4$3dd$1@smc.vnet.net>
In reply to#15050
I think 'IntegerDigits' is the function you want "to pull numbers apart."

On Mon, Jul 1, 2013 at 9:49 PM, <d.a.paxton@gmail.com> wrote:
>
>
> Bob,  Thanks on that.  I see the use of the floor function.  This whole
> idea is trivial when one can use that.  What I am trying to do is basically
> do the floor function as a linear equation.  This is useful for pulling
> numbers apart.  Like a number 13.  How does one algebraically make it 1 and
> 3 or 10 and 3.  Either.
>
>

[toc] | [prev] | [next] | [standalone]


#15109

Fromd.a.paxton@gmail.com
Date2013-07-03 08:50 +0000
Message-ID<kr0ol4$3ea$1@smc.vnet.net>
In reply to#15050
On Saturday, June 29, 2013 2:47:03 AM UTC-6, Richard Fateman wrote:
> Dave --
>
> 1.  You should try to come up with a useful subject line
>
> in the future.
>
> 2. It is called Russian Peasant Multiplication (which you may
>
> find on Google).
>
> 3. There is no reason to believe that a procedural algorithm
>
> has a formula, but in this case I think the inverse is known
>
> as division :)

Thanks for the responses.  IntegerDigits is basically a List function.  If you pluck a number out and use it how does one then bring it back into focus?  I thought about it late last night and there may be a way to do it in base ten.  It gets messy when the starting number is below the base.

  Today I thought to just run to base two and figure it out.  Basically the number ( 13 ) is 1101.  All I have so far is to do a BitAnd of 1.  Like this.  A= BitAnd [13,1],  ( this gives a 1 as 13 is odd ) A is the drop number.  B= number ( 13 in this case ) -A.  The carry number is then B/2.  In this case 6 or 110.  So when marching down the columns of numbers in the multiply this may be the easiest way to go.  I will have to start to fit this into a matrix form and then figure out how to code the left or right diagonals.  That does not seem straight forward at this point.

[toc] | [prev] | [next] | [standalone]


#15116 — Re: Russian Peasant Multiplication / was question on

FromBob Hanlon <hanlonr357@gmail.com>
Date2013-07-03 08:53 +0000
SubjectRe: Russian Peasant Multiplication / was question on
Message-ID<kr0oph$3f2$1@smc.vnet.net>
In reply to#15050
x = RandomInteger[{-1000000, 1000000}]


99333


id = IntegerDigits[x]


{9, 9, 3, 3, 3}


pwr10 = 10^Range[Length[id] - 1, 0, -1]


{10000, 1000, 100, 10, 1}


id*pwr10


{90000, 9000, 300, 30, 3}


x ==
 Sign[x]*id.pwr10 ==
 Sign[x]*Dot[id, pwr10] ==
 Sign[x]*Total[id*pwr10] ==
 Sign[x]*Plus @@ (id*pwr10)


True



Bob Hanlon




On Tue, Jul 2, 2013 at 12:49 AM, <d.a.paxton@gmail.com> wrote:

> On Saturday, June 29, 2013 2:47:03 AM UTC-6, Richard Fateman wrote:
> > Dave --
> >
> > 1.  You should try to come up with a useful subject line
> >
> > in the future.
> >
> > 2. It is called Russian Peasant Multiplication (which you may
> >
> > find on Google).
> >
> > 3. There is no reason to believe that a procedural algorithm
> >
> > has a formula, but in this case I think the inverse is known
> >
> > as division :)
>
> Bob,  Thanks on that.  I see the use of the floor function.  This whole
> idea is trivial when one can use that.  What I am trying to do is basically
> do the floor function as a linear equation.  This is useful for pulling
> numbers apart.  Like a number 13.  How does one algebraically make it 1 and
> 3 or 10 and 3.  Either.
>
>

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web