This page is a mirror of Tepples' nesdev forum mirror (URL TBD).
Last updated on Oct-18-2019 Download

Signed multiplication, division, modulo using lookup table

Signed multiplication, division, modulo using lookup table
by on (#118849)
Is there an algorithm to speed up and use up less code for 16-bit by 16-bit signed multiplication, division, and modulo if you have a 16K byte lookup table in ROM for each of these operations, on a 6502 without decimal mode? Also, can a similar way be done to quickly output a signed 16-bit number in ASCII codes in decimal format?
Re: Signed multiplication, division, modulo using lookup tab
by on (#118850)
One way to work with large decimal numbers quickly is to store them in decimal format, like byte per decimal digit. It could be useful for score display and similar purposes, no need to perform binary to decimal conversion, while adding values isn't that much slower.
Re: Signed multiplication, division, modulo using lookup tab
by on (#118851)
A 16-bit binary to decimal conversion is doable without humongous lookup tables in under 6 scanlines. How many numbers do you intend to print per frame?
Re: Signed multiplication, division, modulo using lookup tab
by on (#118853)
I do know about working with decimal numbers quickly like you described, and have used that (even then I used lookup tables for addition and multiplication). However, it isn't suitable here.

The numbers are stored in binary and I cannot change this; it is a Z-machine interpreter (version 1 to 3 only; therefore lowercase isn't needed, and many other things also aren't needed, but numbers are needed). I don't expect to print many numbers per frame; also, they are not printed directly to the nametables so it doesn't need to be done during vblank. (As far as I know the only things this program need to do in vblank is: blink the cursor, scroll the window to the correct position, dump the text buffer to the screen (if applicable), and clear the bottom two rows (to avoid making the text that has scrolled out of the way visible on TVs that don't overscan).)

I do have a lot of spare ROM space since it is 128K for the story file and 128K for the interpreter, so having lookup tables as large as 16K isn't too much of a problem if they aren't needed for too many things. Much of the program needs to access the story file or needs to run in NMI or whatever so it is stored in the fixed bank; however there is some code in the other banks such as the keyboard reading routine (in the same bank as the decoding table) and some of the initialization.

Other things that might want to be implemented later on are transcript and save game, however I do not intend to implement either of these features at first, due to the difficulty of doing so. For the save game, note that I already have all of the cartridge PRG RAM (64K) used up, and more than six pages of the internal RAM are already used up too. For the transcript, well, I don't know of any printer interface for the Famicom (although maybe it will work fine to just record it on a VCR, but such thing isn't as good as having a printout). In both cases, whatever interface is used has to connect to the tape port or NES controller ports (neither NES port is currently in use), since the expansion port is already used for the keyboard.
Re: Signed multiplication, division, modulo using lookup tab
by on (#118855)
There are some very fast ways to to convert binary to BCD. See the piclist: .../math/radix/b2bu-16b5d.htm
Re: Signed multiplication, division, modulo using lookup tab
by on (#118856)
Binary to decimal was beaten to death many years ago.
Re: Signed multiplication, division, modulo using lookup tab
by on (#118858)
If you don't mind me asking, why do you need the speed? Aren't Z-machine programs all text adventures? These types of games don't require fast interactions or high frame rates, so I'm wondering why this would be a concern to you...
Re: Signed multiplication, division, modulo using lookup tab
by on (#118861)
tokumaru wrote:
If you don't mind me asking, why do you need the speed? Aren't Z-machine programs all text adventures? These types of games don't require fast interactions or high frame rates, so I'm wondering why this would be a concern to you...
I don't need extreme speed, but I wouldn't want it very slow either. Code size is also important although there is a lot of extra ROM banks so they could be used if it would help the code size small and speed fast. (Also, not all Z-machine programs are text adventures, although most are.)
Re: Signed multiplication, division, modulo using lookup tab
by on (#118867)
blargg wrote:
Binary to decimal was beaten to death many years ago.

Need some updated URL love on the mentioned .zip (I tried different URL permutations to no avail); also might want to update your forums' profile home page. *goes back into his hidey hole*
Re: Signed multiplication, division, modulo using lookup tab
by on (#118869)
koitsu wrote:
Need some updated URL love on the mentioned .zip (I tried different URL permutations to no avail)
Yes, that would help. Still, I would like to know if anyone has the information about algorithms for all of these things (binary to decimal is only one of them). In all cases there are signed, but in some cases I may be able to easily modify the algorithms for unsigned to work with signed.

(Note that I have written a program that does arithmetic in decimal: http://esolangs.org/wiki/Deadfish#Unofficial_MagicKit_Assembler)
Re: Signed multiplication, division, modulo using lookup tab
by on (#118870)
zzo38 wrote:
I don't need extreme speed, but I wouldn't want it very slow either.

My point is that it will hardly feel slow to players even if you use the sloppiest non-optimized math routines ever, because there's hardly any action going on. You can probably do around 100 multiplications in a single hardware frame with a decently programmed routine... In a text adventure the player will hardly notice delays of less than 10 frames, so you can do around 1000 multiplications before the player can even start to wonder whether the program is busy... do you really need that much math?

IMO you are trying to optimize something that doesn't need optimizing, and in the process you're just obfuscating your interpreter. Personally, I'd want my code to be clear and easy to follow rather than make use of cryptic tables that will maybe buy me some speed I don't really need.

Quote:
not all Z-machine programs are text adventures

I had never heard of a Z-machine before you mentioned them, could you show me what kind of programs you can make with them?
Re: Signed multiplication, division, modulo using lookup tab
by on (#118871)
There's the standard space-for-time tradeoffs of lookup tables. Multiplication is easy, because it's distributive. For division and remainder, there isn't a good fast accurate general option. Just implement long bitwise division.