Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]

Groups > comp.lang.forth > #27729

Memoization

Show all headers | View raw

I was wondering how easy it would be to implement something like  http://en.wikipedia.org/wiki/Memoization in forth. 

There are a few threads but when I went looking I couldn't find something that was simple, so here is something simple. I hope it's useful.

Using fibonnaci as it’s well known. 

\
\ Win32forth 6.14.03
\ -----------------------------------------------------------------------
\ without memorize 
\


variable c1 \ to count the number of times fib is called

( n -- )
: fib
	1 c1 +!
	dup 0 < if
		2drop abort
	else
		dup 0 = if
			drop 0
		else
			dup 1 = if
				drop 1
			else
				dup 2 - recurse
				swap 1 - recurse
				+
			then
		then
	then
	;

: test ( -- )
	cr
	44 1 do
	0 c1 ! i . i fib . c1 @ . cr
	loop ;


\ -----------------------------------------------------------------------
\ -----------------------------------------------------------------------


\ -----------------------------------------------------------------------
\ using memorize 
\

50 constant memoiz-fibs

variable m1{ \ the argument
	memoiz-fibs cells allot

variable m2{ \ the result
	memoiz-fibs cells allot

variable indx-m \ index into m1,m2

: } ( -- ) cells + ;

( n1 n -- )
: add-memo-fibs
	m1{ indx-m @ } !
	m2{ indx-m @ } !
	1 indx-m +!
	;

( n -- n1 t| f )
: lookup
	false ( -- n flag )

	indx-m @ 0 do
		over m1{ i } @ = if
			drop i true leave
			then
	loop
	if
		m2{ swap } @
		nip true
	else
		drop false
	then
	;

variable c1 \ count of how many times we call the func

( -- )
: init1
		0 indx-m !
		0 0 add-memo-fibs
		1 1 add-memo-fibs
		1 2 add-memo-fibs
	;

defer fib

( n -- )
: fib1
		dup
		dup 2 - fib swap 1 - fib +
		dup rot add-memo-fibs
	;

( n -- )
:noname
	dup 0 < if
		abort
	else
		1 c1 +!
		dup lookup if
			nip
		else
			fib1
		then
	then
		; is fib

: test cr cr
	init1
	44 1 do
		0 c1 !
			i fib i . ."  = " .
		c1 @ . cr
 		loop
	;


For small values it probably doesn't matter, but for larger values the speedup is worth it.  

Back to comp.lang.forth | Previous | Next — Next in thread | Find similar | Unroll thread

Thread

Memoization november.nihal@gmail.com - 2014-01-08 05:05 -0800
  Re: Memoization mhx@iae.nl - 2014-01-08 10:18 -0800

csiph-web