Re: New integer multiplication algorithm

From: Proginoskes (proginoskes_at_email.msn.com)
Date: 02/17/05 

Date: 17 Feb 2005 13:16:00 -0800

fiziwig wrote:
>
> What about even numbers? [...]

For the ultimate application -- factoring -- we won't have to worry
about even numbers. It's easy to tell whether a number is even, no
matter what base it's in. (Either look at the last digit, if the base
is even; or add up the digits, if the base is odd.)

> On another tangent, what about this:
>
> (x,y) = (9,13)
>
> MIN(9,13) = 9 = 1001
> ABS(x-y)/2 = 2 = 0010
>
> 10, 00, 01, 10 -> {2012}
>
> {abcd} # {stuv}
> = 8{a}#(stuv) + 4{b}#(stuv) + 2{c}#(stuv) + {d}#(stuv)
> = 64{a}#{s} + 32{a}#{t} + 16{a}#{u} + 8{a}#{v} +
> 32{b}#{s} + 16{b}#{t} + 8{b}#{u} + 4{b}#{v} +
> 16{c}#{s} + 8{c}#{t} + 4{c}#{u} + 2{c}#{v} +
> 8{d}#{s} + 4{d}#{t} + 2{d}#{u} + {d}#{v}
>
> for {2012} # {2012}
>
> a = s = 2
> b = t = 0
> c = u = 1
> d = v = 2
>
> {2012} # {2012} = 64 + 16 + 8 + 16 + 2 + 8 + 2 + 1 = 117
>
> and, indeed 9 * 13 = 117
>
> However, suppose we express 117 as (1,117)
>
> MIN(1,117) = 1 = 0000001
> ABS(x-y)/2 = 116 = 1110100
>
> 01,01,01,00,01,00,10 -> {1110102}
>
> OR, suppose we express 9 * 13 as 3 * 39 = 117
>
> MIN(3,39) = 3 = 00011
> ABS(x,-y)/2 = 18 = 10010
>
> 01,00,00,11,10 -> {10032}
>
> Now the real challenge is to find out how to get from one to
> the other and show that
>
> {2012} = {10032} = {1110102}

This is NOT what Risto is proposing; Risto is proposing that

     {2012} # {2012} = {10032} # {10032} = {1110102} # {1110102},

which is plausible.

I think Risto's algorithm to multiply works, and that it can be proven
by writing out x and (y - x)/2 (where x <= y) in binary and following
the process through. (This is what the MIN and ABS are doing; setting
up x and (y - x)/2.) I gave out the original post to my problem solving
class, and we may be working through it as a group.

> Because if you can get from {1110102} to any other form, then
> you have the factors.
>
> Another example, 11*31 = 341
>
> (11 ,31) -> {3032}
> (1,341) -> {10101012}
>
> And {3032} = {10101012}
>
> But the trick is to get from the string {10101012}
> to the string {3032}.

... and that's the part which will probably prove tricky; finding all
solutions to the equation x # x = {10101012} # {10101012} probably
can't be done easily, say in polynomial time. (We need to determine
whether there are at least one solution, because one is already present
in the equation.

On yet another tangent, try solving the equation x # {3032} = 341,
which should be "easier" than solving x # x = N.

     --- Christopher Heckman

Relevant Pages

  • Re: writing get_script as an external routine callable by C
    ... I _STRONGLY_ suggest to attend a Perl class or a self-study course where ... If you mean "begins with a digit" as you said above ... Case 2 matches if the beginning of the string is followed by 1 or more ... If you put the two Bushs together in their over seven years of their two ...
    (comp.lang.perl.misc)
  • Re: Sorted Fixed Length String
    ... >I have a String of Numerical Digits Created Using Concatenate. ... >The Strings could be from 6 Characters in Length to 11 Characters in ... >The Least Characters in a String with a Digit GREATER than 1 can ONLY be ... Dim str As String ...
    (microsoft.public.excel.programming)
  • Re: Pi as the Mother Number
    ... For example if we find our 100-digit string starting at the ... 37th digit of pi, we can just say, go to the 37th digit of pi and print the ... problem with using this principle to compress numbers is the problem of the ... Foundation of Mathematics, first to understand the difference between ...
    (sci.math)
  • Re: writing get_script as an external routine callable by C
    ... I _STRONGLY_ suggest to attend a Perl class or a self-study course where ... If you mean "begins with a digit" as you said above ... used as delimiters, therefore it doesn't show up in the FAQ. ... Case 2 matches if the beginning of the string is followed by 1 or more ...
    (comp.lang.perl.misc)
  • Re: a challenge
    ... // if the remainder isn't zero. ... // recursively to convert it to a string ... // of the hundred's digit (there can be only ...
    (alt.lang.asm)
Quantcast