File: numerics.chapt.txt

package info (click to toggle)
yacas 1.3.6-2
  • links: PTS
  • area: main
  • in suites: bullseye, buster, sid, stretch
  • size: 7,176 kB
  • ctags: 3,520
  • sloc: cpp: 13,960; java: 12,602; sh: 11,401; makefile: 552; perl: 517; ansic: 381
file content (338 lines) | stat: -rw-r--r-- 13,337 bytes parent folder | download | duplicates (5)
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
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
			Arbitrary-precision numerical programming

*INTRO This chapter contains functions that help programming numerical calculations with arbitrary precision.

*CMD MultiplyNum --- optimized numerical multiplication
*STD
*CALL
	MultiplyNum(x,y)
	MultiplyNum(x,y,z,...)
	MultiplyNum({x,y,z,...})

*PARMS

{x}, {y}, {z} -- integer, rational or floating-point numbers to multiply

*DESC
The function {MultiplyNum} is used to speed up multiplication of floating-point numbers with rational numbers. Suppose we need to compute $(p/q)*x$ where $p$, $q$ are integers and $x$ is a floating-point number. At high precision, it is faster to multiply $x$ by an integer $p$ and divide by an integer $q$ than to compute $p/q$ to high precision and then multiply by $x$. The function  {MultiplyNum} performs this optimization.

The function accepts any number of arguments (not less than two) or a list of numbers. The result is always a floating-point number (even if {InNumericMode()} returns False).

*SEE MathMultiply

*CMD CachedConstant --- precompute multiple-precision constants
*STD
*CALL
	CachedConstant(cache, Cname, Cfunc)

*PARMS
{cache} -- atom, name of the cache

{Cname} -- atom, name of the constant

{Cfunc} -- expression that evaluates the constant

*DESC

This function is used to create precomputed multiple-precision values of
constants. Caching these values will save time if they are frequently used.

The call to {CachedConstant} defines a new function named {Cname()} that
returns the value of the constant at given precision. If the precision is
increased, the value will be recalculated as necessary, otherwise calling {Cname()} will take very little time.

The parameter {Cfunc} must be an expression that can be evaluated and returns
the value of the desired constant at the current precision. (Most arbitrary-precision mathematical functions do this by default.)

The associative list {cache} contains elements of the form {{Cname, prec, value}}, as illustrated in the example. If this list does not exist, it will be created.

This mechanism is currently used by {N()} to precompute the values of $Pi$ and $gamma$ (and the golden ratio through {GoldenRatio}, and {Catalan}).
The name of the cache for {N()} is {CacheOfConstantsN}.
The code in the function {N()} assigns unevaluated calls to {Internal'Pi()} and {Internal'gamma()} to the atoms {Pi} and {gamma} and declares them to be lazy global variables through {SetGlobalLazyVariable} (with equivalent functions assigned to other constants that are added to the list of cached constants).

The result is that the constants will be recalculated only when they are used in the expression under {N()}.
In other words, the code in {N()} does the equivalent of

	SetGlobalLazyVariable(mypi,Hold(Internal'Pi()));
	SetGlobalLazyVariable(mygamma,Hold(Internal'gamma()));

After this, evaluating an expression such as {1/2+gamma} will call the function {Internal'gamma()} but not the function {Internal'Pi()}.

*EG notest

	In> CachedConstant( my'cache, Ln2, Internal'LnNum(2) )
	Out> True;
	In> Internal'Ln2()
	Out> 0.6931471806;
	In> V(N(Internal'Ln2(),20))
	CachedConstant: Info: constant Ln2 is being
	  recalculated at precision 20 
	Out> 0.69314718055994530942;
	In> my'cache
	Out> {{"Ln2",20,0.69314718055994530942}};


*SEE N, Builtin'Precision'Set, Pi, GoldenRatio, Catalan, gamma

*CMD NewtonNum --- low-level optimized Newton's iterations
*STD
*CALL
	NewtonNum(func, x0, prec0, order)
	NewtonNum(func, x0, prec0)
	NewtonNum(func, x0)

*PARMS

{func} -- a function specifying the iteration sequence

{x0} -- initial value (must be close enough to the root)

{prec0} -- initial precision (at least 4, default 5)

{order} -- convergence order (typically 2 or 3, default 2)

*DESC

This function is an optimized interface for computing Newton's
iteration sequences for numerical solution of equations in arbitrary precision.

{NewtonNum} will iterate the given function starting from the initial
value, until the sequence converges within current precision.
Initially, up to 5 iterations at the initial precision {prec0} is
performed (the low precision is set for speed). The initial value {x0}
must be close enough to the root so that the initial iterations
converge. If the sequence does not produce even a single correct digit
of the root after these initial iterations, an error message is
printed. The default value of the initial precision is 5.

The {order} parameter should give the convergence order of the scheme.
Normally, Newton iteration converges quadratically (so the default
value is {order}=2) but some schemes converge faster and you can speed
up this function by specifying the correct order. (Caution: if you give
{order}=3 but the sequence is actually quadratic, the result will be
silently incorrect. It is safe to use {order}=2.)

*REM
The verbose option {V} can be used to monitor the convergence. The
achieved exact digits should roughly form a geometric progression.

*EG

	In> Builtin'Precision'Set(20)
	Out> True;
	In> NewtonNum({{x}, x+Sin(x)}, 3, 5, 3)
	Out> 3.14159265358979323846;

*SEE Newton

*CMD SumTaylorNum --- optimized numerical evaluation of Taylor series
*STD
*CALL
	SumTaylorNum(x, NthTerm, order)
	SumTaylorNum(x, NthTerm, TermFactor, order)
	SumTaylorNum(x, ZerothTerm, TermFactor, order)

*PARMS

{NthTerm} -- a function specifying $n$-th coefficient of the series

{ZerothTerm} -- value of the $0$-th coefficient of the series

{x} -- number, value of the expansion variable

{TermFactor} -- a function specifying the ratio of $n$-th term to the previous one

{order} -- power of $x$ in the last term

*DESC

{SumTaylorNum} computes a Taylor series $Sum(k,0,n,a[k]*x^k)$
numerically. This function allows very efficient computations of
functions given by Taylor series, although some tweaking of the
parameters is required for good results.

The coefficients $a[k]$ of the Taylor series are given as functions of one integer variable ($k$). It is convenient to pass them to {SumTaylorNum} as closures.
For example, if a function {a(k)} is defined, then
	SumTaylorNum(x, {{k}, a(k)}, n)
computes the series $Sum(k, 0, n, a(k)*x^k)$.

Often a simple relation between successive coefficients $a[k-1]$,
$a[k]$ of the series is available; usually they are related by a
rational factor. In this case, the second form of {SumTaylorNum} should
be used because it will compute the series faster. The function
{TermFactor} applied to an integer $k>=1$ must return the ratio
$a[k]$/$a[k-1]$. (If possible, the function {TermFactor} should return
a rational number and not a floating-point number.) The function
{NthTerm} may also be given, but the current implementation only calls
{NthTerm(0)} and obtains all other coefficients by using {TermFactor}.
Instead of the function {NthTerm}, a number giving the $0$-th term can be given.

The algorithm is described elsewhere in the documentation.
The number of terms {order}+1
must be specified and a sufficiently high precision must be preset in
advance to achieve the desired accuracy.
(The function {SumTaylorNum} does not change the current precision.)

*E.G.
To compute 20 digits of $Exp(1)$ using the Taylor series, one needs 21
digits of working precision and 21 terms of the series. 

	In> Builtin'Precision'Set(21)
	Out> True;
	In> SumTaylorNum(1, {{k},1/k!}, 21)
	Out> 2.718281828459045235351;
	In> SumTaylorNum(1, 1, {{k},1/k}, 21)
	Out> 2.71828182845904523535;
	In> SumTaylorNum(1, {{k},1/k!}, {{k},1/k}, 21)
	Out> 2.71828182845904523535;
	In> RoundTo(N(Ln(%)),20)
	Out> 1;


*SEE Taylor

*CMD IntPowerNum --- optimized computation of integer powers
*STD
*CALL
	IntPowerNum(x, n, mult, unity)

*PARMS

{x} -- a number or an expression

{n} -- a non-negative integer (power to raise {x} to)

{mult} -- a function that performs one multiplication

{unity} -- value of the unity with respect to that multiplication

*DESC

{IntPowerNum} computes the power $x^n$ using the fast binary algorithm.
It can compute integer powers with $n>=0$ in any ring where multiplication with unity is defined.
The multiplication function and the unity element must be specified.
The number of multiplications is no more than $2*Ln(n)/Ln(2)$.

Mathematically, this function is a generalization of {MathPower} to rings other than that of real numbers.

In the current implementation, the {unity} argument is only used when the given power {n} is zero.

*E.G.

For efficient numerical calculations, the {MathMultiply} function can be passed:
	In> IntPowerNum(3, 3, MathMultiply,1)
	Out> 27;
Otherwise, the usual {*} operator suffices:
	In> IntPowerNum(3+4*I, 3, *,1)
	Out> Complex(-117,44);
	In> IntPowerNum(HilbertMatrix(2), 4, *,
	  Identity(2))
	Out> {{289/144,29/27},{29/27,745/1296}};
Compute $Mod(3^100,7)$:
	In> IntPowerNum(3,100,{{x,y},Mod(x*y,7)},1)
	Out> 4;

*SEE MultiplyNum, MathPower, MatrixPower

*CMD BinSplitNum --- computations of series by the binary splitting method
*CMD BinSplitData --- computations of series by the binary splitting method
*CMD BinSplitFinal --- computations of series by the binary splitting method
*STD
*CALL
	BinSplitNum(n1, n2, a, b, c, d)
	BinSplitData(n1,n2, a, b, c, d)
	BinSplitFinal({P,Q,B,T})

*PARMS

{n1}, {n2} -- integers, initial and final indices for summation

{a}, {b}, {c}, {d} -- functions of one argument, coefficients of the series

{P}, {Q}, {B}, {T} -- numbers, intermediate data as returned by {BinSplitData}

*DESC

The binary splitting method is an efficient way to evaluate many series when fast multiplication is available and when the series contains only rational numbers.
The function {BinSplitNum} evaluates a series of the form
$$ S(n[1],n[2])=Sum(k,n[1],n[2], a(k)/b(k)*(p(0)/q(0)) * ... * p(k)/q(k)) $$.
Most series for elementary and special functions at rational points are of this form when the functions $a(k)$, $b(k)$, $p(k)$, $q(k)$ are chosen appropriately.

The last four arguments of {BinSplitNum} are functions of one argument that give the coefficients $a(k)$, $b(k)$, $p(k)$, $q(k)$.
In most cases these will be short integers that are simple to determine.
The binary splitting method will work also for non-integer coefficients, but the calculation will take much longer in that case.

Note: the binary splitting method outperforms the straightforward summation only if the multiplication of integers is faster than quadratic in the number of digits.
See <*the algorithm documentation|yacasdoc://Algo/3/14/*> for more information.

The two other functions are low-level functions that allow a finer control over the calculation.
The use of the low-level routines allows checkpointing or parallelization of a binary splitting calculation.

The binary splitting method recursively reduces the calculation of $S(n[1],n[2])$ to the same calculation for the two halves of the interval [$n[1]$, $n[2]$].
The intermediate results of a binary splitting calculation are returned by {BinSplitData} and consist of four integers $P$, $Q$, $B$, $T$.
These four integers are converted into the final answer $S$ by the routine {BinSplitFinal} using the relation
$$ S = T / (B*Q) $$.

*E.G.

Compute the series for $e=Exp(1)$ using binary splitting.
(We start from $n=1$ to simplify the coefficient functions.)
	In> Builtin'Precision'Set(21)
	Out> True;
	In>  BinSplitNum(1,21, {{k},1},
	  {{k},1},{{k},1},{{k},k})
	Out> 1.718281828459045235359;
	In> N(Exp(1)-1)
	Out> 1.71828182845904523536;
	In>  BinSplitData(1,21, {{k},1},
	  {{k},1},{{k},1},{{k},k})
	Out> {1,51090942171709440000,1,
	  87788637532500240022};
	In> BinSplitFinal(%)
	Out> 1.718281828459045235359;

*SEE SumTaylorNum

*CMD MathSetExactBits --- manipulate precision of floating-point numbers
*CMD MathGetExactBits --- manipulate precision of floating-point numbers
*CORE
*CALL
	MathGetExactBits(x)
	MathSetExactBits(x,bits)

*PARMS
{x} -- an expression evaluating to a floating-point number

{bits} -- integer, number of bits 

*DESC
Each floating-point number in Yacas has an internal precision counter that stores the number of exact bits in the mantissa.
The number of exact bits is automatically updated after each arithmetic operation to reflect the gain or loss of precision due to round-off.
The functions {MathGetExactBits}, {MathSetExactBits} allow to query or set the precision flags of individual number objects.

{MathGetExactBits(x)} returns an integer number $n$ such that {x} represents a real number in the interval [$x*(1-2^(-n))$, $x*(1+2^(-n))$] if $x!=0$ and in the interval [$-2^(-n)$, $2^(-n)$] if $x=0$.
The integer $n$ is always nonnegative unless {x} is zero (a "floating zero").
A floating zero can have a negative value of the number $n$ of exact bits.

These functions are only meaningful for floating-point numbers.
(All integers are always exact.)
For integer {x}, the function {MathGetExactBits} returns the bit count of {x}
and the function {MathSetExactBits} returns the unmodified integer {x}.

*REM FIXME - these examples currently do not work because of bugs

*E.G.
The default precision of 10 decimals corresponds to 33 bits:
	In> MathGetExactBits(1000.123)
	Out> 33;
	In> x:=MathSetExactBits(10., 20)
	Out> 10.;
	In> MathGetExactBits(x)
	Out> 20;
Prepare a "floating zero" representing an interval [-4, 4]:
	In> x:=MathSetExactBits(0., -2)
	Out> 0.;
	In> x=0
	Out> True;

*SEE Builtin'Precision'Set, Builtin'Precision'Get