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

Groups > comp.lang.c++ > #7024 > unrolled thread

(simple?) problem with multiplication

Back to article view | Back to comp.lang.c++

Contents

  (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-21 11:04 -0700
    Re: (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-21 11:11 -0700
    Re: (simple?) problem with multiplication "Balog Pal" <pasa@lib.hu> - 2011-06-21 20:35 +0200
      Re: (simple?) problem with multiplication Anonymous <anonymous@no.net> - 2011-06-21 20:45 +0200
      Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-21 14:46 -0400
        Re: (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-21 12:03 -0700
          Re: (simple?) problem with multiplication Gido <gido0001@gmail.com> - 2011-06-21 14:30 -0700
            Re: (simple?) problem with multiplication Anonymous <anonymous@no.net> - 2011-06-21 23:32 +0200
            Re: (simple?) problem with multiplication Juha Nieminen <nospam@thanks.invalid> - 2011-06-23 06:33 +0000
    Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-21 14:40 -0400
    Re: (simple?) problem with multiplication Christopher <cpisz@austin.rr.com> - 2011-06-21 11:39 -0700
    Re: (simple?) problem with multiplication Anonymous <anonymous@no.net> - 2011-06-21 23:32 +0200
      Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-21 23:41 +0200
    Re: (simple?) problem with multiplication Rune Allnor <allnor@tele.ntnu.no> - 2011-06-21 21:33 -0700
      Re: (simple?) problem with multiplication Ttodir <sanmrtn96@gmail.com> - 2011-06-22 04:59 -0700
    Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-22 06:55 -0700
      Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-22 10:10 -0400
        Re: (simple?) problem with multiplication Leigh Johnston <leigh@i42.co.uk> - 2011-06-22 15:19 +0100
          Re: (simple?) problem with multiplication Dilip <rdilipk@gmail.com> - 2011-06-22 07:33 -0700
            Re: (simple?) problem with multiplication Leigh Johnston <leigh@i42.co.uk> - 2011-06-22 15:39 +0100
              Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-22 11:02 -0400
                Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-23 23:45 +0100
            Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-22 23:59 -0700
        Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-22 23:50 -0700
          Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-23 09:26 +0100
    Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-22 21:24 +0100
      Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-24 00:00 +0100
    Re: (simple?) problem with multiplication gwowen <gwowen@gmail.com> - 2011-06-24 01:42 -0700
      Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-24 10:47 +0100
    Re: (simple?) problem with multiplication SG <s.gesemann@gmail.com> - 2011-06-24 10:09 -0700
      Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-24 13:32 -0400
        Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-24 20:07 +0200
          Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-24 14:14 -0400
            Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-24 20:28 +0200
              Re: (simple?) problem with multiplication Pete Becker <pete@versatilecoding.com> - 2011-06-24 16:26 -0400
                Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 03:01 +0100
                  Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 18:20 +0100
              Re: (simple?) problem with multiplication "Alf P. Steinbach /Usenet" <alf.p.steinbach+usenet@gmail.com> - 2011-06-25 04:21 +0200
              Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 10:12 +0100
                Re: (simple?) problem with multiplication SG <s.gesemann@gmail.com> - 2011-06-25 02:51 -0700
                  Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 11:19 +0100
                  Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 11:19 +0100
                  Re: (simple?) problem with multiplication Gareth Owen <gwowen@gmail.com> - 2011-06-26 07:59 +0100
                    Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-26 12:34 +0100
            Re: (simple?) problem with multiplication SG <s.gesemann@gmail.com> - 2011-06-25 02:37 -0700
          Re: (simple?) problem with multiplication Gareth Owen <gwowen@gmail.com> - 2011-06-25 08:58 +0100
            Re: (simple?) problem with multiplication "Paul" <pchristor@yahoo.co.uk> - 2011-06-25 10:00 +0100
            Re: (simple?) problem with multiplication Kai-Uwe Bux <jkherciueh@gmx.net> - 2011-06-25 10:29 +0200

Page 3 of 3 — ← Prev page 1 2 [3]

#7151

"SG" <s.gesemann@gmail.com> wrote in message 
news:c4f86897-98de-4b62-b9a8-26a7ed50b7ce@u26g2000vby.googlegroups.com...
> On 25 Jun., 11:12, Paul wrote:
>> [...]
>> My interpretation of that is that it's unproven bullshit.
>>
>> Lets see this magical "modified double and add algorithm" that, for you,
>> solves the problem
>
> Hmmm. It seems like I expected too much from you guys in terms of
> reading comprehension, google skills, and education.
>
> "double and add" for multiplication is the little brother of
> "square and multiply" for computing powers.
>
> Here it is:
> http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add
>
> Also, I explained "modified" with a "that includes the mod-reduction"
> in my initial post. In case you have no idea what the purpose of this
> modification is: It's to avoid _overflows_.
>
> *sigh*
>

I know what shift and add means, but I don't know what your modified shift 
and add means.
I want to see your modified shift and add algorithm that solves this 
problem..

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

#7155

"SG" <s.gesemann@gmail.com> wrote in message 
news:c4f86897-98de-4b62-b9a8-26a7ed50b7ce@u26g2000vby.googlegroups.com...
> On 25 Jun., 11:12, Paul wrote:
>> [...]
>> My interpretation of that is that it's unproven bullshit.
>>
>> Lets see this magical "modified double and add algorithm" that, for you,
>> solves the problem
>
> Hmmm. It seems like I expected too much from you guys in terms of
> reading comprehension, google skills, and education.
>
> "double and add" for multiplication is the little brother of
> "square and multiply" for computing powers.
>
> Here it is:
> http://en.wikipedia.org/wiki/Multiplication_algorithm#Shift_and_add
>
> Also, I explained "modified" with a "that includes the mod-reduction"
> in my initial post. In case you have no idea what the purpose of this
> modification is: It's to avoid _overflows_.
>
> *sigh*
>

I know what shift and add means, but I don't know what your modified shift 
and add means.
I want to see your modified shift and add algorithm that solves this 
problem..

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

#7166

SG <s.gesemann@gmail.com> writes:
>
> *sigh*
>

Put Paul in a killfile, and sigh no more.[0]

[0] 87.9% of respondents said their quality of life improved.

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

#7172

"Gareth Owen" <gwowen@gmail.com> wrote in message 
news:8739ixyt6f.fsf@gmail.com...
> SG <s.gesemann@gmail.com> writes:
>>
>> *sigh*
>>
>
> Put Paul in a killfile, and sigh no more.[0]
>
> [0] 87.9% of respondents said their quality of life improved.
>

gwowen has tried and failed to solve this problem, Its his loss if he 
killfiled me because obviously I am the superior programmer because I solved 
the problem and he didn't <shrug>.

You seem to think you can produce some modified double and add algorithm, 
which I think is doubtfull. If you can lets see it, if you can't just 
*sigh*. Killfiling me won't help you either way :)

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

#7149

On 24 Jun., 20:14, Pete Becker wrote:
> On 2011-06-24 14:07:45 -0400, Kai-Uwe Bux said:
> > Pete Becker wrote:
> >> On 2011-06-24 13:09:56 -0400, SG said:
>
> >>> In case this hasn't been mentioned already (I just skimmed this
> >>> thread):
>
> >>> (a*b)%B = ((a%B)*(b%B))%B
>
> >> Yes, but it doesn't solve the problem. :-( Suppose a*b overflows and
> >> that B is greater than both a and b. Then a%B is a, and b%B is b; then
> >> (a%B)*(b%B) is a*b, and it overflows.

This was (the uninteresting) part of the solution. You snipped the
rest. Obviously the whole line is not even well-formed C nor C++ code
since the left side is an rvalue. I simply used C's %-syntax for a
_mathematical_equation_. You seem to have ignored my reference to
"modified double-and-add algorithm" (the interesting part of the
solution).

> > That seems to be vicious snipping on your part. SG said:
> "Vicious"? Really?

Yes, it was. You've overlooked something.

> Um, if the expression ((a%B)*(b%B)) overflows the behavior is

If you copy&paste it into a source code file, of course. But at no
place I suggested to compute

  ((a%B)*(b%B))

I suggested to compute

  ((a%B)*(b%B))%B    <-- as a mathematical expression, not a C
expression

VIA a _modified_double-and-add_algorithm_. And by that I don't mean
copy&paste this thing into source code. I expected people to use their
brain and read the whole post. It's not my job to implement this
algorithm and show it here for what looks like a homework question.

As for the reduced signal-to-bullshit ratio, I'm afraid you're not
completely innocent in this case.

Cheers!
SG

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

#7145

Kai-Uwe Bux <jkherciueh@gmx.net> writes:

> That said, a version of double-and-add for modulo arithmetic has been 
> proposed elsethread; and that version at least did assume that 2*(a%B) does 
> not overflow.

My double-and-add version did have an overflow check.  It's a simple
problem - its only the details are a pain.

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

#7147

"Gareth Owen" <gwowen@gmail.com> wrote in message 
news:87hb7ewdej.fsf@gmail.com...
> Kai-Uwe Bux <jkherciueh@gmx.net> writes:
>
>> That said, a version of double-and-add for modulo arithmetic has been
>> proposed elsethread; and that version at least did assume that 2*(a%B) 
>> does
>> not overflow.
>
> My double-and-add version did have an overflow check.  It's a simple
> problem - its only the details are a pain.
>
Its so simple that you cannot provide a solution? lol very good.

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

#7152

Gareth Owen wrote:

> Kai-Uwe Bux <jkherciueh@gmx.net> writes:
> 
>> That said, a version of double-and-add for modulo arithmetic has been
>> proposed elsethread; and that version at least did assume that 2*(a%B)
>> does not overflow.
> 
> My double-and-add version did have an overflow check.  It's a simple
> problem - its only the details are a pain.

Oops: I didn't see yours, whence I was not specific enough. The above should 
have specifically referred to this proposal by Anonymous:

  replace c with B in the below code, and long long with int, then test it

  /* this function calculates (a*b)%c taking into account that a*b might 
  overflow */
  long long mulmod(long long a,long long b,long long c){
     long long x = 0,y=a%c;
     while(b > 0){
         if(b%2 == 1){
             x = (x+y)%c;
         }
         y = (y*2)%c;
         b /= 2;
     }
     return x%c;
  }


Best,

Kai-Uwe Bux

[toc] | [prev] | [standalone]

Page 3 of 3 — ← Prev page 1 2 [3]

Back to top | Article view | comp.lang.c++

csiph-web