1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
|
/* [wxMaxima batch file version 1] [ DO NOT EDIT BY HAND! ]*/
/* [ Created with wxMaxima version 25.04.0-DevelopmentSnapshot ] */
/* [wxMaxima: title start ]
Memoizing
[wxMaxima: title end ] */
/* [wxMaxima: section start ]
Introduction
[wxMaxima: section end ] */
/* [wxMaxima: comment start ]
Maxima is largely based on lists, so for beginners it is always surprising that trying to construct a list on-the-fly creates an altogether different kind of object:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
x[1]:5;
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
One hint to that is the label that tells we only declared x[1]. Another hint is that maxima tells us that x isn't a list:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
listp(x);
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
It still remembers what x contains, though.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
x[1];
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
We also can add a second element to x:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
x[5]:10;
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
Show what x is.
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
arrayinfo(x);
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
x[gnu]:30;
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
Hash maps work fine. The only thing that one can stumble about is that if we redefine "gnu" x[gnu] will read the redefined value:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
gnu:5;
x[gnu];
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
The tick (') operator can forbid maxima to do so:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
x['gnu];
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
Hash maps have many uses. One is to implement memoizing:
[wxMaxima: comment end ] */
/* [wxMaxima: section start ]
Memoizing using hash maps
[wxMaxima: section end ] */
/* [wxMaxima: comment start ]
Memoizing provides big speed-ups if one wants to calculate something that is hard to calculate and of which only relatively few items ever need to be calculated.
[wxMaxima: comment end ] */
/* [wxMaxima: comment start ]
As an example let's construct a hash array primes[n] where each entry n contains the nth prime number, at least within the bounds of accuracy of primep():
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
? primep;
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
primes[1]:1;
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
primes[n]:=block([i], /* block([i],...) makes i a local variable */
i:primes[n-1]+1,
while not primep(i) do
i:i+1,
return(i)
);
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
If we now calculate the 1000th prime maxima will store the info about the first 1000 primes in a hash map:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
primes[100];
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
arrayinfo(primes);
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
Calculating primes[1000] in one go requires to calculate primes[999], which in turn requires to calculate primes[998], which (as this effectively is a recursive function call) eventually exceeds the lisp's stack limit. Calculating primes[1000] in several steps is possible, instead:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
primes[100];
primes[200];
primes[300];
primes[400];
primes[500];
primes[600];
primes[700];
primes[800];
primes[900];
primes[1000];
/* [wxMaxima: input end ] */
/* [wxMaxima: comment start ]
Memoizing should speed up accessing already-known values. Let's test if that is the case:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
showtime:true$
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
primes[1100];
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
primes[1100];
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
showtime:false$
/* [wxMaxima: input end ] */
/* [wxMaxima: section start ]
Memoizing functions
[wxMaxima: section end ] */
/* [wxMaxima: comment start ]
Maxima additionally allows to define memoizing functions: Functions that calculate the output value that corresponds to an input value only once and then remember them for the future.
[wxMaxima: comment end ] */
/* [wxMaxima: comment start ]
Let's create a function that generates and remembers Fibonacci numbers for us:
[wxMaxima: comment end ] */
/* [wxMaxima: input start ] */
fib[n]:=if n < 3 then 1 else fib[n-1] + fib[n-2];
/* [wxMaxima: input end ] */
/* [wxMaxima: input start ] */
fib[10];
/* [wxMaxima: input end ] */
/* Old versions of Maxima abort on loading files that end in a comment. */
"Created with wxMaxima 25.04.0-DevelopmentSnapshot"$
|
