anton@mips.complang.tuwien.ac.at (Anton Ertl) writes:
>Als naechstes werde ich wohl einen anderen, besseren Loesungsansatz
>implementieren.
Also, dann, hier ist er: Wir verwenden einfache eine Tabelle aller
Summen I^3+J^3. Wenn eine Summe ein zweites mal vorkommt, haben wir
eine Loesung gefunden. Das folgende Program implementiert die Tabelle
mit Hilfe von Gforth's TABLE, daher ist es nicht portabel, und auch
nicht berauschend schnell, aber bei 1290 als Eingabe immer noch
mehrmals so schnell wie die portable Version von Marcels Programm (auf
Gforth aehnlich schnell wie das andere Programm auf vfxlin, mit ein
bisschen Tricksen sogar noch schneller). Es braucht auch eine
betraechtliche Menge Speicher (bei 1290 als Eingabe 26MB dictionary
auf einem 32-bit System allein fuer die Tabelle mit 827816 Elementen),
aber das koennen wir uns heutzutage ja leisten.
Ein Vorteil des Programms ist, dass es viel offensichtlicher ist, dass
es korrekt ist; und tatsaechlich liefert es bei der Eingabe 1290 als
Ergebnis 2298 Zahlen, waehrend man die doppelten Zahlen bei meiner
Korrektur von Marcels Programm erst nachtreaeglich herausfiltern muss.
Weiters nennt es noch zusaetzliche Loesungen fuer die gleiche Zahl,
ohne sie zu zaehlen. Beispielausgaben:
....
1944219375 = 1167^3 + 708^3 = 1240^3 + 335^3
1958102848 = 1023^3 + 961^3 = 1240^3 + 372^3
Another solution for 1915865217: 1242^3 + 9^3
....
2298 numbers
Zur Geschwindigkeit:
1.51user 0.10system 0:01.63elapsed vfxlin 'include ramanujans-taxi.fs bye'
1.51user 0.06system 0:01.58elapsed gforth-fast -m 1G -e "1290 include rama-taxi.fs cr bye"
1.01user 0.07system 0:01.08elapsed gforth-fast -m 1G -e ": x 20 to hashbits hashdouble ; x 1290 include rama-taxi.fs cr bye"
Verbesserungsmoeglichkeiten:
- Das Programm portabel machen. Eine einfache Variante waere, eine
WORDLIST statt der TABLE zu verwenden, die Zahl in einen String zu
verwandeln (damit die case insensitivity nicht stoert) und das
NEXTNAME CREATE durch ['] CREATE EXECUTE-PARSING zu ersetzen. Da
wuerde sich dann zeigen, welches Forth-System die effizienteste
Dictionary-Implementierung hat. Das mache ich vielleicht.
- Eine eigene Tabellen-Datenstruktur implementieren, die effizienter
ist. Eventuell koennte man die so organisieren, dass eine sortierte
Ausgabe der Zahlen moeglich ist; dann koennte man die ausgegebenen
Loesungen wirklich sinnvoll durchnummerieren, und die Ausgabe von
Tripeln etc. in einer Zeile durchfuehren (statt ueber die Ausgabe
verteilt wie jetzt).
- Speichersparen. Fuer laengere Suchen, wenn einem der Speicher doch
ausgehen wuerde: Blockweises Abarbeiten der Summen: Zuerst alle von
0..10^12, dann von 10^12..8*10^12, dann 8*10^12..27*10^12, ...
Die letzten beiden Schritte mache ich wohl nicht.
- anton
Hier ist das Gforth-Programm:
\ Ramanujan's Taxi
\ print integer solutions to the equation I^3+J^3 = K^3+L^3
\ usage: gforth -m 1G -e "1290 include rama-taxi.fs bye"
\ to print all solutions, where I, J, K, L < 1290
\ for more information read VD 3+4/2007 or
\
http://www.durangobill.com/Ramanujan.html
table constant cube-sums
variable solutions 0 solutions !
: cubed ( n1 -- n2 )
dup dup * * ;
variable tmp
: insert-sum ( n1 n2 -- )
get-current >r
cube-sums set-current tmp 1 cells nextname create
r> set-current
0 , 2, ;
: .sum ( -- )
tmp @ 12 u.r ;
: .pair ( n1 n2 -- )
4 u.r ." ^3 + " 4 u.r ." ^3" ;
: found-solution ( n1 n2 xt -- )
cr execute >r
r@ @ if ( n1 n2 )
." Another solution for " .sum ." : "
else
.sum ." = " r@ cell+ 2@ .pair ." = "
1 solutions +!
endif
.pair
1 r> +! ;
: check-taxi ( n1 n2 -- )
over cubed over cubed + tmp !
tmp 1 cells cube-sums search-wordlist if ( n1 n2 xt )
found-solution
else ( n1 n2 )
insert-sum
endif ;
: rama-taxis ( n -- )
1 u+do
i 1 u+do
i j check-taxi
loop
loop ;
( n ) rama-taxis cr solutions @ . .( numbers)
Ramanujan's Taxi 
Linear Mode
