🚀 go-pugleaf

Daniel Seagraves wrote:
> Anyway, the question is, how do computers multiply?  And no, I don't mean
> cyber-sex.  [Yeah, that was bad.  Gomen...] I mean a mathematical
> multiply.  'Cause right now IMUL is doing odd things.  To make it more
> interesting, Mirian wrote the math stuff and I don't understand how it
> works, so trying to fix it will get interesting...

To multiply two 36-bit unsigned numbers, "n1" and "n2" and
generate a 72-bit "product":

product=0
do i=1 to 36
  shift n2 to the right, watching what falls off the end
  if a "1" fell off the end, product=product+n1
  shift n1 to the left
end do

Most real computers have hardware assist for this procedure, so that
either the entire operation is done instantaneously or the shifting
and adding is done several bits at a time.

And to further complicate matters, real computers usually have sign
conventions (ones or twos complement).  If you're having difficulties,
I suspect it has to do with the signs.  Are you writing your emulator
on a machine that's ones or twos complement?

Tim.

Daniel Seagraves wrote:
>
>     [snip...]     [snip...]     [snip...]
>
> Anyway, the question is, how do computers multiply?  And no, I don't mean
> cyber-sex.  [Yeah, that was bad.  Gomen...] I mean a mathematical
> multiply.  'Cause right now IMUL is doing odd things.  To make it more
> interesting, Mirian wrote the math stuff and I don't understand how it
> works, so trying to fix it will get interesting...
>
Check out "Booth's algorithm".  Use a good search engine (or even use
HOTBOT like *I* do), and you can probably find some useful info.  The
good things about Booth's algorithm are that it handles *any* mix of
signed integers, and it usually requires *fewer* additions than other
multiply algorithms.

If yo do *not* find anything you can use, I have an old Kilobaud magazine
somewhere with an article on Booth's algorithm.  If you need it, I can either
snail-mail you a copy, or maybe scan it in and email you the files.

--
+-------------------------------------------------------------+
|     Charles and Francis Richmond     <richmond@plano.net>   |
+-------------------------------------------------------------+

On Tue, 15 Jun 1999, Tim Shoppa wrote:

> Most real computers have hardware assist for this procedure, so that
> either the entire operation is done instantaneously or the shifting
> and adding is done several bits at a time.

I'm not gonna bother emulating that...

> And to further complicate matters, real computers usually have sign
> conventions (ones or twos complement).  If you're having difficulties,
> I suspect it has to do with the signs.  Are you writing your emulator
> on a machine that's ones or twos complement?

Will it matter?  I'm trying to keep as far away from being dependent on
the crappy Intel architecture I'm using, 'bcause Intel sucks. All I really
wanna care about is if the bit is set or not, and I use GCC's unsigned
long long so the host machine's sign convention doesn't screw with it.
(Oh, and explain ones vs twos complement, please!  Or, I could go look it
up...)

Daniel Seagraves | I'm an International Clandestine Arms Dealer!
"In the name of the moon, will you punish me?" - SMS #104
"There is nothing more dangerous than a resourceful idiot." - Dilbert
SailorMoon Into Eternity! | Usagi's Stormtroopers Local #42 | 36 BITS 4EVER!

In article <Pine.LNX.4.10.9906171531230.12161-100000@bony.umtec.com>,
Daniel Seagraves <root@bony.umtec.com> wrote:


> Will it matter?  I'm trying to keep as far away from being dependent on
> the crappy Intel architecture I'm using, 'bcause Intel sucks. All I really
> wanna care about is if the bit is set or not, and I use GCC's unsigned
> long long so the host machine's sign convention doesn't screw with it.
> (Oh, and explain ones vs twos complement, please!  Or, I could go look it
> up...)

With one's complement negation, the machine word in question is simply
complemented (imagine a four-bit machine word, and use a monospace font):

+5 ------->  0101
-5 ------->  1010

This gives you the following possibilities:

+0    0000     -0     1111  (Yup, Negative Zero!)
+1    0001     -1     1110
+2    0010     -2     1101
+3    0011     -3     1100
+4    0100     -4     1011
+5    0101     -5     1010
+6    0110     -6     1001
+7    0111     -7     1000

When you add a one's complement number then take the complement, you get
the effect of subtraction:

+7            0111
-3            1100
Add           ----
              1011
Complement    ----
+4            0100


Two's complement works a little slicker, once the number is complemented,
you add 1 to the result:

+0    0000     -0     1111 + 1 --->  0000 (Ignore the overflow!)
+1    0001     -1     1110 + 1 --->  1111
+2    0010     -2     1101 + 1 --->  1110
+3    0011     -3     1100 + 1 --->  1101
+4    0100     -4     1011 + 1 --->  1100
+5    0101     -5     1010 + 1 --->  1011
+6    0110     -6     1001 + 1 --->  1010
+7    0111     -7     1000 + 1 --->  1001
-------------- -8     -------------  1000

Notice that +8 doesn't exist, the bit pattern for -8 is simply a left-over
possibility that's used occassionally in address calculations.  The high
bit is set, so it must be a negative number.  Some systems ignore the
highest negative number to keep the set of integers symmetrical.

Regardless, when you add a positive integer to a negative, here's what happens:

+5           0101
-4           1100
Add          ---- (Ignore the overflow!)
+1           0001

Just for the sake of argument, using 1000 as a number gives the following
results:

+5           0101
-8           1000
Add          ----
-3           1101

Hope this helps!

In article <Pine.LNX.4.10.9906171531230.12161-100000@bony.umtec.com>,
Daniel Seagraves  <root@bony.umtec.com> wrote:
>(Oh, and explain ones vs twos complement, please!  Or, I could go look it
>up...)

Someone else already explained what it is, and anyway you don't find one's
comp machines any more (certainly not running C code!), however it does turn
up in IP and TCP checksums;  I don't know if this is the main reason why,
but one cute thing about it is that add/sub are byte-order-independent in
one's complement.  The reason is, whenever you add two one's comp numbers
and get carry out from the adder, that means that you must have crossed the
boundary from -0 (all ones) to +0 (all zeros), which shouldn't count for
anything but a regular full adder doesn't know that, so you add the carry
back in to correct the result (since it's too low by one due to the gap).
So essentially, you have carry from the MSB to the LSB, and of course as
usual you have carry between the two middle bits (just like any other pair
of contiguous bits), so you can add up your checksum in either order and get
the correct result (in the same order).  Real handy for doing TCP/IP checksums
on a little-endian machine, and neither style of machine has to byte-swap.

What I can't understand is why so many TCP/IP implementors don't realize
that the reason you store the one's complement of the sum, is so that the
recipient can check it by taking the sum of the whole record (including
the complemented sum) and if it's correct you get 0 (or actually -0 unless
the record is all +0s).  Yet for some reason most TCP/IP implementations
seem to check the checksum by clearing it to 0, re-computing the checksum,
complementing it, and seeing if it matches the original value.  Extra work!

John Wilson
D Bit

John Wilson wrote:
>
> In article <Pine.LNX.4.10.9906171531230.12161-100000@bony.umtec.com>,
> Daniel Seagraves  <root@bony.umtec.com> wrote:
> >(Oh, and explain ones vs twos complement, please!  Or, I could go look it
> >up...)
>
> Someone else already explained what it is, and anyway you don't find one's
> comp machines any more (certainly not running C code!), however it does turn

Not to be too contentious, but the machine I write OS code for is still
a 36 bit, one's complement machine.  And we have a C compiler, and it
certainly appears to generate working code...

<snip>
>
> John Wilson
> D Bit

Regards,

David W. Schroth

On 18 Jun 1999, John Wilson wrote:

> In article <Pine.LNX.4.10.9906171531230.12161-100000@bony.umtec.com>,
> Daniel Seagraves  <root@bony.umtec.com> wrote:
> >(Oh, and explain ones vs twos complement, please!  Or, I could go look it
> >up...)
>
> Someone else already explained what it is, and anyway you don't find one's
> comp machines any more (certainly not running C code!)

Erm, Toad has a C compiler...

Daniel Seagraves | I'm an International Clandestine Arms Dealer!
"In the name of the moon, will you punish me?" - SMS #104
"There is nothing more dangerous than a resourceful idiot." - Dilbert
SailorMoon Into Eternity! | Usagi's Stormtroopers Local #42 | 36 BITS 4EVER!

"David W. Schroth" <David.Schroth@unisys.com> writes:

> Not to be too contentious, but the machine I write OS code for is still
> a 36 bit, one's complement machine.  And we have a C compiler, and it
> certainly appears to generate working code...

Oh, do tell! The 1100 series lives? What's the current hardware
implementation? Sounds like the perfect platform for PDP-10 emulation,
or perhaps Multics...

--
-Stephen H. Westin
Any information or opinions in this message are mine: they do not
represent the position of Cornell University or any of its sponsors.

In article <376A7805.CC992FD2@unisys.com>,
David W. Schroth <David.Schroth@unisys.com> wrote:
>Not to be too contentious, but the machine I write OS code for is still
>a 36 bit, one's complement machine.  And we have a C compiler, and it
>certainly appears to generate working code...

My hat is off to you!  I'd love to hear what kind of machine this is.

My point about C is not that it's not possible to write a C compiler for
a one's comp machine, but that the typical C source code that's around is
likely to have hidden dependences on a two's comp architecture, and the
authors probably don't even know it.  Since that kind of thing tends to come
up in the low-level (but not low enough!) bit fiddling that's common in C.
Of course the code still compiles w/o errors, so it's got to be a real pain
for porting.  To harp on the same example:  if something like Kermit tried
to compute a checksum of a block by just adding up all the 8-bit bytes and
ignoring overflow along the way, that would work fine on a two's comp machine,
but would likely get the wrong answer on a one's comp machine.

Is anyone still running BCD machines?  Now *that* would make life really
interesting for C!

John Wilson
D Bit

"Stephen H. Westin" wrote:
>
> "David W. Schroth" <David.Schroth@unisys.com> writes:
>
> > Not to be too contentious, but the machine I write OS code for is still
> > a 36 bit, one's complement machine.  And we have a C compiler, and it
> > certainly appears to generate working code...
>
> Oh, do tell! The 1100 series lives? What's the current hardware
> implementation? Sounds like the perfect platform for PDP-10 emulation,
> or perhaps Multics...
>

Yes, the 1100 series (or its descendants) still live.  I'm not clear on
what we *call* it these days (it was the 2200 series for a while, it
might be the IX series now - all marketing nonsense).  I'm not sure what
you mean by "What's the current hardware implementation?" - my best
guess for the answer you're looking for is that it is currently
implemented in CMOS (as opposed to ECL).  The architecture has changed
some through the years - it's still segmented, but now it uses paging as
well.  I suspect that Multics might fit reasonably well (ignoring picky
little details like not having access to the code), as several of the
newer architecture features look a lot like the features of Multics.
And I do agree with John Wilson's observation on the difficulties of
porting C code - I haven't done it, but I'm told that there are a bunch
of subtle gotchas that invariably do getcha...

> --
> -Stephen H. Westin
> Any information or opinions in this message are mine: they do not
> represent the position of Cornell University or any of its sponsors.

Regards,

David W. Schroth

In article <Pine.LNX.4.10.9906181231370.13031-100000@bony.umtec.com>
Daniel Seagraves <root@bony.umtec.com> writes:

>On 18 Jun 1999, John Wilson wrote:

>> Someone else already explained what it is, and anyway you don't find one's
>> comp machines any more (certainly not running C code!)

>Erm, Toad has a C compiler...

But the Toad-1 is a two's-complement architecture...
--
Rich Alderson			Last LOTS Tops-20 Systems Programmer, 1984-1991
				Current maintainer, MIT TECO EMACS (v. 170)
last name @ XKL dot COM		Chief systems administrator, XKL LLC, 1998-now

In article <376a5abe.0@news.wizvax.net>, John Wilson <wilson@dbit.com> wrote:
>Someone else already explained what it is, and anyway you don't find one's
>comp machines any more (certainly not running C code!),

Unisys 1100 was a 36 bit ones-complement mainframe with a UNIX emulation
package available (SX-1100, we called it sucks). I believe there are still
1100s in operation.

--
This is The Reverend Peter da Silva's Boring Sig File - there are no references
to Wolves, Kibo, Discordianism, or The Church of the Subgenius in this document

           "Be vewy vewy quiet...I'm hunting Jedi." -- Darth Fudd

On 18 Jun 1999, Richard M. Alderson III wrote:

> >Erm, Toad has a C compiler...
>
> But the Toad-1 is a two's-complement architecture...

Bleh, so I was wrong then.  Shoot me.

*ducks the resulting hail of gunfire* Figuratively!  I meant Figuratively!

Daniel Seagraves | I'm an International Clandestine Arms Dealer!
"In the name of the moon, will you punish me?" - SMS #104
"There is nothing more dangerous than a resourceful idiot." - Dilbert
SailorMoon Into Eternity! | Usagi's Stormtroopers Local #42 | 36 BITS 4EVER!