OT: primitive mult/div algorithms  Printable Version + HP Forums (https://archived.hpcalc.org/museumforum) + Forum: HP Museum Forums (https://archived.hpcalc.org/museumforum/forum1.html) + Forum: Old HP Forum Archives (https://archived.hpcalc.org/museumforum/forum2.html) + Thread: OT: primitive mult/div algorithms (/thread222928.html) 
OT: primitive mult/div algorithms  Egan Ford  05242012 Hello all, I am look for some very fast integer mult/div algorithms for 8 and 16 bit systems. Mult is easy using tables (e.g. http://www.6502.org/source/integers/fastmult.htm), but I have not found anything like this for div. Before I started working it out for myself I thought I'd try to see what was already out there.
Thanks.
Re: OT: primitive mult/div algorithms  Bob Patton  05242012 About 2 weeks ago I finally tossed a set of notes from my Kim1 microprocessor class of 1977. This included handdrawn flow charts and a listing for integer division. I first thought: "Murphy's Law." Then I remembered saving all the blankbacked papers for scratch. Yep; still have them. The algorithm wasn't declared to be particularly fast, but if it might be useful, I could scan and email. I think the Kim1 used a 6502 chip.
Re: OT: primitive mult/div algorithms  Garth Wilson  05242012 How much memory can you afford for tables? I'm preparing a section of my website http://wilsonminesco.com/ to have Intel Hex files for large lookup tables for 16bit fixedpoint/scaledinteger math in EPROM (or you can load them into RAM if you wish). I hope to eventually be able to supply the EPROMs too for those who want them but don't have a way to program them. Most of the tables are 128KB (65,536 16bit answers), for trig and log functions, multiplication, squareroot, etc.. The table of inverses is 256KB, because each of the 65,536 answers is 32bit. You can multiply by the inverse to speed up the divide, and use the 256x256 multiplication table to speed up the multiplication too. These can be used with any 8bitter, but will need banking or other I/O hardware to access the 2MB if the processor only has a 16bit address bus. Looking up functions in precalculated tables that give all 16 bits correct is much faster than a single multiplication, let alone many multiplications and divisions as would otherwise be needed for some functions. I calculated the tables and formed the Intel Hex files using the HP71. The actual HP71 programs will be on the website too, in case any one is interested and might to take it further and form additional tables. On the same website you referenced, my solution to the common 6502 division bug is at http://www.6502.org/source/integers/ummodfix/ummodfix.htm . Bruce clark has a version that's supposedly slightly faster on the 6502 wiki at http://6502org.wikidot.com/softwaremath .
Edited: 24 May 2012, 11:17 p.m.
Re: OT: primitive mult/div algorithms  Egan Ford  05252012 Quote:Bob, that would be great. I'd love to examine them. Please send to egan@sense.net
Thanks again. BTW, no rush, take your time.
Re: OT: primitive mult/div algorithms  Egan Ford  05252012 Quote:12K. Quote:This one (http://6502org.wikidot.com/softwaremathfastdiv) seem interesting, but I need more information.
Thanks again.
Re: OT: primitive mult/div algorithms  Mike T.  05252012 I have or possibly had though I don't remember throwing them out a pile of bound volumes of early PCW issues.
Where abouts are you..?
Re: OT: primitive mult/div algorithms  Garth Wilson  05262012 Quote:You can also interface a large ROM through I/O. I've even done it through a 6522's synchronous serial port and shift registers, with three wires, and it was still faster than actually calculating the answers.Quote:12K. Re: OT: primitive mult/div algorithms  Egan Ford  05262012 Quote:Salt Lake City. Re: OT: primitive mult/div algorithms  Gerson W. Barbosa  05262012 While not the fastest multiplication algorithm around, Russian peasant multiplication is interesting and easy to implement. Once I used it for arbitrary length integer multiplication on the Z80 microprocessor. The following is a simple 8bit operands, 16bit result Z80 program: org $c000 ; sorry, no comments.The equivalent 6502 code below is somewhat lengthy, but someone not so rusty at 6502 assembly language programming as I am might be able to make it shorter: * = $0300This can be assembled at http://www.masswerk.at/6502/assembler.html, giving the following objectcode: AD 40 03 85 00 AD 41 03As I didn't find an online hex to dec convert that would convert all bytes at once, I did it on Emu71: 10 DESTROY ALLThe AppleWin emulator can be used to test this and other algorithms: 10 HOME : PRINT "ENTER A,B" Gerson.
Edited: 26 May 2012, 6:07 p.m.
Re: OT: primitive mult/div algorithms  Egan Ford  05272012 Very interesting. Thanks.
