Egyptian Division

[ChrisCrawford]

Here's something I wish we had known forty years ago: there's an algorithm known as "Egyptian division" that executes integer division using nothing but addition and doubling. This can be executed on a 6502, and would have opened up all sorts of possibilities. There were, of course, floating point packages available for the 6502, but they ate up a lot of cycles, whereas this algorithm is really fast. I'm willing to write up an explanation of the algorithm to go along with an explanation of my old "Mayan line drawing" algorithm. I'd like to know if the Egyptian division algorithm is already well known among 6502 enthusiasts. What say you?

[thorfdbg]

On 4/20/2021 at 5:09 PM, ChrisCrawford said:

Here's something I wish we had known forty years ago: there's an algorithm known as "Egyptian division" that executes integer division using nothing but addition and doubling. What say you?

That's the standard (binary) division algorithm on the 6502 anyhow. See for example Rodney Zak's "Programming the 6502". The algorithm is actually "divising by two and compare", and the problem with that in the mathpack is that  the math pack uses BCD arithmetics and there is no simple way to divide a BCD number by 2. Or at least no way that would make a significantly faster algorithm than the one we have right now.

[ChrisCrawford]

Thanks for clearing that up for me. I recall asking various programmers at Atari but nobody seemed to be aware of that algorithm back in 1979. Odd. Maybe I just asked the wrong people. 

[+gnusto]

On 4/20/2021 at 8:09 AM, ChrisCrawford said:

"Mayan line drawing" algorithm

 

First off, I guess hi Chris? Is that the real you? I feel like this deserves some recognition ?

 

I'm not familiar with mayan law drawing. Is it more efficient than Bresenham, which can be expressed entirely with integer math and bit shifting?

[ChrisCrawford]

Yes, what I call "the Mayan algorithm" looks to be a variation on Bresenham's. Again, I am surprised that nobody at Atari seemed to be aware of it, as we had some really top-notch graphics people there. It's starting to look as if I DEFINITELY didn't ask the right people! ?

 

By the way, I developed that algorithm for my 2600 game Wizard, which was never published but is now bouncing around the Net. And it does correctly draw lines at arbitrary angles, and even detects blocking objects. All in a few hundred bytes of code. 

[Tempest]

54 minutes ago, ChrisCrawford said:

Yes, what I call "the Mayan algorithm" looks to be a variation on Bresenham's. Again, I am surprised that nobody at Atari seemed to be aware of it, as we had some really top-notch graphics people there. It's starting to look as if I DEFINITELY didn't ask the right people! ?

 

By the way, I developed that algorithm for my 2600 game Wizard, which was never published but is now bouncing around the Net. And it does correctly draw lines at arbitrary angles, and even detects blocking objects. All in a few hundred bytes of code. 

Can you talk a bit about Wizard?  I did a review of it for my page ages ago, but I'd like to hear anything you can add.

 

http://www.atariprotos.com/2600/software/wizard/wizard.htm

[+DrVenkman]

Well, since you are evidently *THE* Chris Crawford, welcome! And thanks for all the great memories.  

 

You might find it amusing that one of your creations is the topic of another very recent thread:

 

 

[+gnusto]

1 hour ago, ChrisCrawford said:

Again, I am surprised that nobody at Atari seemed to be aware of it, as we had some really top-notch graphics people there.

 

It is indeed surprising. I believe it was in fairly common usage in the 8 bit era, certainly by the time I was learning 6502 in the early 80s it was. I remember coming across it first as a physical print routine where it was also popular due to being non-overlapping - the less you printed in those days, the better! I saw different approaches of incremental error (using the leftover for weighting instead of the full float value) usage until the 90's, when co processors melded into the CPU and eventually became so hyper optimized that floats were net faster than ints for such usage.

 

It's good to see you here on AtariAge. Thank you for the many late hours with Eastern Front or Balance of Power, among others (but in particular I remember Balance of Power on my Amiga).

[ChrisCrawford]

Wizard was spec'd as a 2K game, but just four months later, when it was ready, the marketing people had decided that everything should be 4K, so they asked me if I could expand it to 4K. To be honest, I really didn't want to work on the 2600 -- I was eager to get going on the 800. So I told them that you don't just expand a 2K game to 4K: you start from scratch and design it for 4K from the ground up. That was true, and marketing lost interest, so I got to move to the 800.

 

As to the cassette problem with Scram, the first thing to try is to carefully clean the tape head with a Q-tip soaked in alcohol. Wipe vigorously; you can't hurt the head with a Q-tip. Then give it lots of time for every molecule of alcohol to evaporate away, then try to load the cassette. Another possibility is to try again with a new recorder. If you ever do get it loaded, then SAVE it to a new tape!!!!

 

If everything else fails, there's one last desperate trick you can use: freeze the tape. Wrap it tightly in a zip-lock bag, make sure that there's no extra air inside. Stick it in the deep freeze and give it overnight to come to temperature. When it's good and cold, pop it out of the fridge, shove it into the cassette player, and load immediately. You may well damage the tape if it sticks to itself. But with some luck, it might just load. This crazy stunt actually worked for me several times. But this is definitely a Do-or-Die solution. 

[Rybags]

Welcome Chris!

I can remember a few shortcut topics here for binary maths, might have even started one myself.  Might have been Russian multiplication.

And too right, if we had some of these tricks in the day things might have been different.  Of course most of them were around but the hive mind was little bulletin boards and that was if we were lucky.

 

Brought back memory for me too - I think it was in Creative Computing around 1983/4.  Can still remember your story about the creation of Eastern Front - great bit of reading.

Edited April 22, 2021 by Rybags

[dmsc]

Hi all!

 

I suspect most early computer algorithms were rediscovered multiple times in the home computers, because we did not had easy access to all the information!

 

About math algorithms, those were known and used from the early history, and binary floating-point algorithms are published from the 1950's. In the 6502 you can find implementation of multiplication and division as old as the Woz 6502 FP math, that uses a lot of tricks to make the code small.

 

About the graphics algorithms, the Atari OS has an implementation of the Bresenham algorithm for line drawing, and the equivalent circle-drawing algorithm was also known, as shown in the article from 1983, were it is called "potential", and a 6502 assembly version is given: https://www.atarimagazines.com/compute/issue38/066_1_CIRCLES.php

 

Have Fun!

[+slx]

On 4/22/2021 at 5:16 AM, ChrisCrawford said:

As to the cassette problem with Scram, the first thing to try is to carefully clean the tape head with a Q-tip soaked in alcohol. Wipe vigorously; you can't hurt the head with a Q-tip. Then give it lots of time for every molecule of alcohol to evaporate away, then try to load the cassette. Another possibility is to try again with a new recorder. If you ever do get it loaded, then SAVE it to a new tape!!!! 

Thanks for contributing here, it's an honour to read from one of the giants of Atari software here.

 

The problem with Scram wasn't about loading as it affected a copy on a virtual floppy in an emulator. As visible on the screenshot above, there seems to be some "P/M graphics debris" that overlays the text window when used on an Atari800MacX emulator.

 

BTW, are you aware of why Scram was never officially released on floppy disc?

[playermissile]

On 4/22/2021 at 4:48 AM, Rybags said:

Brought back memory for me too - I think it was in Creative Computing around 1983/4.  Can still remember your story about the creation of Eastern Front - great bit of reading.

Yes, I enjoyed the reminiscences in that article very much. It was the August 1982 issue of Creative Computing, which I covered in episode 25 of the podcast. His writing has such great detail that it took me 12 minutes of audio to cover it.

[+MrFish]

Chris has another account that he's been using here before.

 

@Chris Crawford