Binary Division Algorithms?

Hi,

Can someone recommend a site with binary division algorithms? I'm tryihg to understand the PDP-1 DIS instruction (below). As described it doesn't work by itself. Any information on this algorithm would be appreciated.

Gary

Divide Step (10 usec) dis Y Operation Code 56

The Accumulator and the In-Out Register are rotated left one place. IO Bit

17 receives the complement of AC Bit 0. If IO Bit 17 is ONE, the C(Y) are subtraced from C(AC). If IO Bit 17 is ZERO, C(Y) + 1 are added to C(AC). This instruction is used in the divide subroutine A result of minus zero is changed to plus zero.
Reply to
Abby Brown
Loading thread data ...

Are you familiar with the shift-and-accumulate algorithm for multiplying binary numbers? You can do division the same way, except you shift and conditionally subtract instead. It works just like long division. It sounds like that instruction is equivalent to one step of the process.

I don't have specific examples, offhand.

Why the PDP, are you programming one? How nostalgic. :-)

Tim

--
Deep Friar: a very philosophical monk.
Website: http://webpages.charter.net/dawill/tmoranwms
 Click to see the full signature
Reply to
Tim Williams

If you can find it, "Electronic computers: A Made Simple Book" ("for dummies" books before it was the fashion to insult the reading public) by Henry Jacobowitz, 1963 (LOC card # 62-7648)

has a few pages on division algorithms. I'd take a few hi-res picture if I hadn't left my camera at work. I'm not scanning this book, it'll crack the spine.

Reply to
a7yvm109gf5d1

formatting link

Reply to
a7yvm109gf5d1

Take a look at Analog Devices' documentation on the ADSP-21xx DSP chip and look for their DIVS and DIVQ instructions. There is a nice logic diagram there, which may be helpful when taken together with their other written documentation about it.

Jon

Reply to
Jon Kirwan

I think this site details the divide algorithm used in the PDP-1.

formatting link

I may still have a very early chess program listing for the PDP2 in the loft. It wasn't very strong and tended to cheat in tricky positions announcing "PDL overflow" and reflecting bishops of the board edges.

Regards, Martin Brown

Reply to
Martin Brown

hg to

work

t

ed

From the PDP-1 Handbook:

formatting link
MMING_PDP-1 see also
formatting link

(N.B. The PDP-1 uses 1's complement arithmetic and 18-bit words. Also, the bits are designated opposite to current usage, i.e. bit 17 is the LSB and bit 0 is the MSB))

Divide (30 to 40 usec, except on overflow, 12 usec) div Y Operation Code 56

"The dividend must be in the AC and IO registers in the form indicated in the instruction, Multiply. IO bit 17 is ignored. The divisor is the C(Y). At the completion of the instruction, the C(AC) are the quotient and the C(IO) are the remainder. The sign of the remainder (in IO bit zero) is the sign of the dividend. The instruction that follows a DIV will be skipped unless an overflow occurs. The C(Y) are not affected by this instruction. If the remainder or quotient result is minus zero, that value is changed to plus zero."

"If the magnitude of the high order part of the dividend is equal to or greater than the magnitude of the divisor, and overflow is indicated. In this case, the following instruction is not skipped. The original C(AC) and C(IO) are restored. The overflow flip-flop is not affected. "

-- Joe

Reply to
J.A. Legris

In some large libraries, I've seen copiers designed for books - the glass goes all the way up to the edge of the machine, with more glass down the side, abutting it. It's designed for copying book pages without cracking the spine. :-)

The last time I used one, it was 15 cents a copy - it's probably up to a quarter by now. ;-)

Hope This Helps! Rich

Reply to
Rich Grise

I would love a copy if you can find it. PDP-1 programs are a bit difficult to come by.

TIA, Gary

Reply to
Abby Brown

I implemented shift -and-accumulate for the hardware divide instruction, "div." I also implemented the "dis" instruction per above. It isn't essential to understand the "dis" for my purposes but I would like to. Some background: the early PDP-1s implemented the "dis" instruction. Latter modifications implemented a full hardware divide, "div." They use the same op-code.

I used to have a book with many such algorithms but it must of been victim of some housecleaning.

Building one. I started programming on a PDP-1. I've always wanted to build a working model and I'm not getting any younger. I have most of a software prototype done.

The summer between my freshman and sophomore year I found one of MIT's PDP-1s which had Spacewar and air conditioning. That redirected by career from physics to computers. Years later I employed one of the authors of Spacewar and we remained friends. He has offered to write the diagnostics for my machine.

Gary

Reply to
Abby Brown

I can discuss them. There are lots of sites, but it's hard to imagine one that will help here.

It appears to be a single step. After discovering (I didn't know) that IO is 18 bits, it seemed likely to me that 18 such instructions would be needed in sequence. That in hand, I discovered this from the spacewar code:

And sure enough, I count 18 of them.

This description of either add or subtract suggests what is called a "non-restoring division" algorithm to me. You might look these up. I don't know enough about the DIS Y instruction operands. But I gather that it involves an AC, an IO, and a memory location identified in the instruction itself by address and just called Y, which I assume is the divisor -- possibly conditioned before use.

As such, the block diagram in the ADSP-2100 Family User's Manual for the DIVQ instruction will probably help a little. Similar approach.

I gather that the ALU looks like this for add and subtract:

from memory ,--------, latch | | | | | ------ ------ | \ \ / / | \ \ / / | \ v / | \ / | \ / | ------- | | | | | [ AC LATCH ] | | | '--------------'

However, for the DIS instruction, the IO register is involved. I'm also guessing from the testual description you provided together with how I know it must have worked, that bit 17 is the lower order bit and not the higher order one? And that bit 1 is the highest order? (Bit

0 is sign??) Otherwise it doesn't make sense to me.

If I'm on the right track generally and not completely off-base, I think I can explain it to you. Even never having ever seen a PDP-1 or read its documentation. But if I got the bit order wrong, then I'm lost, too.

Jon

Reply to
Jon Kirwan

// Spacewar! was conceived in 1961 by Martin Graetz, Stephen Russell, // and Wayne Wiitanen. It was first realized on the PDP-1 in 1962 by // Stephen Russell, Peter Samson, Dan Edwards, and Martin Graetz, // together with Alan Kotok, Steve Piner, and Robert A Saunders. // Spacewar! is in the public domain, but this credit paragraph must // accompany all distributed versions of the program.

Interesting. I was a physics major that got exposed to programming as part of the course-work.

Jon

Reply to
Jon Kirwan

I will try to find it over the Xmas holidays. There is an effort being made at present to collect together the source for all the important prehistoric chess programs. This one dates back to the 1970's and was originally written by Arthur Norman the Lisp advocate. It used a pretty odd vector graphics display which means you would have to rewrite the display code. The latter was excellent for black hole and asteroids.

Regards, Martin Brown

Reply to
Martin Brown

Thanks, that helped. The MIT RLE PDP-1 I used had hardware divide so I wasn't aware that Spacewar ever used "dis". The version of Spacewar I have (the 1963 version, likely the one you have) does in fact use "dis". A few hours of reverse engineering (the muddle mind of a PDP-1 programmer was an ugly thing) yielded

sub dvr ; Subtract divisor from AC sma ; Skip if divisor less than AC (ie, no overflow) jmp ovf ; Overflow, dividend too large to divide dis dvr ; do n of these for n bits, in our case, n=18 add dvr ; Correct for first sub

The obvious advantage of the "dis" algorithm is provision for overflow detection. Also, there might have been some hardware or timing advantages specific to the PDP-1.

Shag Graetz came over and we looked at the code segment. He showed me the patch he had made to accomodate the hardware divide, non-trivial because all timing was done by instruction count. He left me his listing of the original 1962 version of Spacewar plus some other stuff. I want to throw everything I can through the software model before commiting to hardware.

A google search for "non-restoring division" yielded a couple of instances of an algorithm but not the one I'm interested in. The ADSP algorithm also appeared not to match.

Thanks again, Gary

Reply to
Abby Brown

Only you can decide that. However, the instruction description you posted is recognizable as part of a non-restoring approach to division. The storage of the numbers I admit zero knowledge about, though. It may be one's complement notation, for all I know. But that isn't hard to deal with.

I'm not sure from your comment whether you are referring to the logic diagram (which is NOT typically what is described as an algorithm) or the code samples they also provide (which is an algorithm.)

My imagination allowed me to see a close match in the logic layout, even without knowing the binary notation format of the PDP-1. I didn't say exact and didn't mean to imply a perfect match. I'd have hoped that would have been understood. But I felt it would help with some basic knowledge and some imagination to work out the gaps.

In any case, I could take your instruction description and translate it into what's going on mathematically. I just don't know what you want. To understand the whys and wherefores of that particular implementation, the class of non restoring division generally, or what....

However, since you've got access to Shag Graetz, I've a hunch you don't need me there. He can probably clarify all these details.

You still didn't confirm for me if I'd gotten the bit order correct or discuss the notational format. If I got the bit order wrong, I'll have to admit I'm all wet and should be ignored. If I did get it correct and if you are interested in the recurrence logic, I might be of some small help -- all I'll need is the notation description for the words (one's or two's complement, etc.) The rest falls out.

Jon

Reply to
Jon Kirwan

tryihg to

doesn't work

Bit

are

used

zero.

formatting link

There is something inconsistent here. Only 2's complement machines have = negative zero.

Reply to
JosephKK

formatting link

negative zero.

Want to try that again? There is no negative zero in two's complement. It is 1's (and '9's) complement that there are two representations of zero (all '1's is negative zero and all '0's is positive zero).

Reply to
krw

negative zero.

Instead there is one asymmetric negative number -2^(n-1) that cannot be represented as a positive value. ABS(x) can be a problem sometimes.

Signed magnitude arithmetic also has two zero representations.

Regards, Martin Brown

Reply to
Martin Brown

formatting link

Reply to
Ben Bradley

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.