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

Groups > comp.lang.forth > #27729 > unrolled thread

Memoization

Back to article view | Back to comp.lang.forth

Contents

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

#27729 — Memoization

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.  

[toc] | [next] | [standalone]

#27737

On Wednesday, January 8, 2014 2:05:33 PM UTC+1, novembe...@gmail.com wrote:
> I was wondering how easy it would be to implement something like  http://en.wikipedia.org/wiki/Memoization in forth. 
[ skipping reams of code ]
> For small values it probably doesn't matter, but for larger values the speedup
> is worth it.

CREATE _fib HERE  #47 CELLS ALLOT
: fib ( n1 -- n2 ) RECURSIVE
    dup 2 < IF  drop 1 exit  THEN
    dup _fib swap cells + @ DUP IF  NIP EXIT ELSE  DROP  THEN
    dup >R 
    dup  1- fib
    swap 2- fib + 
    DUP _fib R> cells + ! ;

-marcel

[toc] | [prev] | [standalone]

Back to top | Article view | comp.lang.forth

csiph-web