The following warnings occurred:
Warning [2] Undefined array key 222928 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 222933 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 222939 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223059 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223061 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223062 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223102 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223119 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223152 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223214 - Line: 275 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 275 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $thread - Line: 295 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 295 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Trying to access array offset on value of type null - Line: 295 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 295 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $fid - Line: 295 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 295 errorHandler->error_callback
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223059 - Line: 331 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 331 errorHandler->error_callback
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 304 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223102 - Line: 331 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 331 errorHandler->error_callback
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 304 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223119 - Line: 331 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 331 errorHandler->error_callback
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 304 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined array key 223214 - Line: 331 - File: inc/plugins/threaded_mode.php PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php 331 errorHandler->error_callback
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 332 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 304 ThreadedMode::buildtree
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $theme - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Trying to access array offset on value of type null - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $theme - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Trying to access array offset on value of type null - Line: 3 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 3 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Undefined variable $lang - Line: 5 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 5 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks
Warning [2] Attempt to read property "messages_in_thread" on null - Line: 5 - File: inc/plugins/threaded_mode.php(305) : eval()'d code PHP 8.1.2-1ubuntu2.14 (Linux)
File Line Function
/inc/class_error.php 153 errorHandler->error
/inc/plugins/threaded_mode.php(305) : eval()'d code 5 errorHandler->error_callback
/inc/plugins/threaded_mode.php 305 eval
/inc/plugins/threaded_mode.php 23 ThreadedMode::showthread_threaded
/inc/class_plugins.php 142 threaded_mode_showthread_threaded
/showthread.php 918 pluginSystem->run_hooks





OT: primitive mult/div algorithms



#4

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.


#5

About 2 weeks ago I finally tossed a set of notes from my Kim-1 microprocessor class of 1977. This included hand-drawn flow charts and a listing for integer division. I first thought: "Murphy's Law." Then I remembered saving all the blank-backed 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 e-mail. I think the Kim-1 used a 6502 chip.


#6

Quote:
The algorithm wasn't declared to be particularly fast, but if it might be useful, I could scan and e-mail. I think the Kim-1 used a 6502 chip.

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.

#7

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 look-up tables for 16-bit fixed-point/scaled-integer 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 16-bit answers), for trig and log functions, multiplication, square-root, etc.. The table of inverses is 256KB, because each of the 65,536 answers is 32-bit. 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 8-bitter, but will need banking or other I/O hardware to access the 2MB if the processor only has a 16-bit address bus. Looking up functions in pre-calculated 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 HP-71. The actual HP-71 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/software-math .

Edited: 24 May 2012, 11:17 p.m.


#8

Quote:
How much memory can you afford for tables?

1-2K.
Quote:
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/software-math .

This one (http://6502org.wikidot.com/software-math-fastdiv) seem interesting, but I need more information.

Thanks again.


#9

Quote:
Quote:
How much memory can you afford for tables?
1-2K.
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.
#10

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..?


#11

Quote:
Where abouts are you..?

Salt Lake City.
#12

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 8-bit operands, 16-bit result Z80 program:

	org $c000              ; sorry, no comments.
ld hl,0
ld c,$ff
ld de,$ff
loop: ld a,c
cp 0
ret z
and 1
jr z,loop0
add hl,de
loop0: srl c
sla e
rl d
jr loop
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:
        * = $0300               
LDA $0340
STA *$00
LDA $0341
STA *$01
LDA #$00
STA *$02
STA *$03
STA *$04
LOOP LDA *$00
BEQ END
AND #$01
BEQ LOOP0
CLC
LDA $01
ADC *$03
STA *$03
LDA $02
ADC *$04
STA *$04
LOOP0 LSR *$00
ASL *$01
ROL *$02
JMP LOOP
END RTS
This can be assembled at http://www.masswerk.at/6502/assembler.html, giving the following object-code:
AD 40 03 85 00 AD 41 03
85 01 A9 00 85 02 85 03
85 04 A5 00 F0 1C 29 01
F0 0F 18 AD 01 00 65 03
85 03 AD 02 00 65 04 85
04 46 00 06 01 26 02 4C
12 03 60
As I didn't find an online hex to dec convert that would convert all bytes at once, I did it on Emu71:
10 DESTROY ALL
20 FOR I=1 TO 51
30 READ B$
40 PRINT HTD(B$);
50 NEXT I
60 DATA AD, 40, 03, 85, 00, AD, 41, 03, 85, 01, A9, 00, 85, 02, 85, 03, 85
70 DATA 04, A5, 00, F0, 1C, 29, 01, F0, 0F, 18, AD, 01, 00, 65, 03, 85, 03
80 DATA AD, 02, 00, 65, 04, 85, 04, 46, 00, 06, 01, 26, 02, 4C, 12, 03, 60
The AppleWin emulator can be used to test this and other algorithms:
 10  HOME : PRINT "ENTER A,B"
20 FOR I = 768 TO 818
30 READ BT: POKE I,BT
40 NEXT I
50 INPUT A,B: POKE 832,A: POKE
833,B
60 CALL 768: PRINT "A * B = "; PEEK
(3) + 256 * PEEK (4)
70 DATA 173,64,3,133,0,173,65,
3,133,1,169,0,133,2,133,3,13
3
80 DATA 4,165,0,240,28,41,1,24
0,15,24,173,1,0,101,3,133,3
90 DATA 173,2,0,101,4,133,4,70
,0,6,1,38,2,76,18,3,96

RUN

ENTER A,B
?217,253
A * B = 54901
]

Gerson.


Edited: 26 May 2012, 6:07 p.m.


#13

Very interesting. Thanks.


Possibly Related Threads…
Thread Author Replies Views Last Post
  OT--TI-36X Algorithms Matt Agajanian 48 11,064 09-01-2013, 08:13 PM
Last Post: robert rozee
  HELP WANTED ON ALGORITHMS Joerg Woerner 19 4,855 04-27-2013, 12:56 PM
Last Post: Eric Smith
  OT: Sorting algorithms as dances Thomas Klemm 2 1,149 04-12-2011, 09:31 AM
Last Post: Tim Wessman
  Corvallis Division - DIV.39 Joerg Woerner 3 1,476 09-13-2010, 04:15 PM
Last Post: Martin Pinckney
  Re: New Root Seeking Algorithms Hans de Moor 1 874 11-14-2007, 02:38 PM
Last Post: hugh steers
  Re: New Root Seeking Algorithms hugh steers 1 851 11-11-2007, 05:21 PM
Last Post: hugh steers
  New Root Seeking Algorithms Namir 13 2,987 11-08-2007, 03:54 PM
Last Post: Namir
  Algorithms in the 21S Arnaud Amiel 2 1,055 04-15-2005, 12:55 PM
Last Post: Arnaud Amiel
  HP Algorithms eclectic_echidna 0 675 10-18-2003, 03:35 PM
Last Post: eclectic_echidna
  12C and its financial algorithms Eduardo 7 2,014 06-19-2003, 04:48 PM
Last Post: hugh

Forum Jump: