Formal power series: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl}}: Fix comment: Perl 6 --> Raku) |
|||
Line 1,768: | Line 1,768: | ||
taylor(fcos(x)^2 + fsin(x)^2, x, 0, 20); |
taylor(fcos(x)^2 + fsin(x)^2, x, 0, 20); |
||
/ * 1 + ... * /</lang> |
/ * 1 + ... * /</lang> |
||
=={{header|Nim}}== |
|||
===Using C algorithm=== |
|||
The program is based on C algorithm but uses rationals instead of floats. There are many other differences in order to use Nim facilities (for instance, function and operator overloading) and some parts were borrowed from Kotlin version. |
|||
<lang Nim>import rationals, tables |
|||
type |
|||
Fraction = Rational[int] |
|||
FpsKind = enum fpsConst, fpsAdd, fpsSub, fpsMul, fpsDiv, fpsDeriv, fpsInteg |
|||
Fps = ref object |
|||
kind: FpsKind |
|||
s1, s2: Fps |
|||
a0: Fraction |
|||
cache: Table[Natural, Fraction] |
|||
const |
|||
Zero: Fraction = 0 // 1 |
|||
One: Fraction = 1 // 1 |
|||
DispTerm = 12 |
|||
XVar = "x" |
|||
Super: array['0'..'9', string] = ["⁰", "¹", "²", "³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `$`(fract: Fraction): string = |
|||
## Return the representation of a fraction without the denominator if it is equal to 1. |
|||
if fract.den == 1: $fract.num else: rationals.`$`(fract) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc exponent(n: Natural): string = |
|||
## Return the representation of an exponent using unicode superscript. |
|||
if n == 1: return "" |
|||
for d in $n: result.add(Super[d]) |
|||
#################################################################################################### |
|||
# FPS. |
|||
func newFps*(val = 0): Fps = |
|||
## Build a FPS of kind fpsConst using the given integer value. |
|||
Fps(kind: fpsConst, a0: val // 1) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func newFps*(val: Fraction): Fps = |
|||
## Build a FPS of kind fpsConst using the given fraction. |
|||
Fps(kind: fpsConst, a0: val) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func newFps*(op: FpsKind; x: Fps; y: Fps = nil): Fps = |
|||
## Build a FPS for a unary or binary operation. |
|||
Fps(kind: op, s1: x, s2: y, a0: Zero) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func redefine*(fps: Fps; other: Fps) = |
|||
## Redefine a FPS, modifying its kind ans its operands. |
|||
fps.kind = other.kind |
|||
fps.s1 = other.s1 |
|||
fps.s2 = other.s2 |
|||
#--------------------------------------------------------------------------------------------------- |
|||
## Operations on FPS. |
|||
func `+`*(x, y: Fps): Fps = newFps(fpsAdd, x, y) |
|||
func `-`*(x, y: Fps): Fps = newFps(fpsSub, x, y) |
|||
func `*`*(x, y: Fps): Fps = newFps(fpsMul, x, y) |
|||
func `/`*(x, y: Fps): Fps = newFps(fpsDiv, x, y) |
|||
func derivative*(x: Fps): Fps = newFps(fpsDeriv, x) |
|||
func integral*(x: Fps): Fps = newFps(fpsInteg, x) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func `[]`*(fps: Fps; n: Natural): Fraction = |
|||
## Return the nth term of the FPS. |
|||
if n in fps.cache: return fps.cache[n] |
|||
case fps.kind |
|||
of fpsConst: |
|||
result = if n > 0: Zero else: fps.a0 |
|||
of fpsAdd: |
|||
result = fps.s1[n] + fps.s2[n] |
|||
of fpsSub: |
|||
result = fps.s1[n] - fps.s2[n] |
|||
of fpsMul: |
|||
result = Zero |
|||
for i in 0..n: result += fps.s1[i] * fps.s2[n - i] |
|||
of fpsDiv: |
|||
let d = fps.s2[0] |
|||
if d == Zero: raise newException(DivByZeroDefect, "Division by null fraction") |
|||
result = fps.s1[n] |
|||
for i in 1..n: result -= fps.s2[i] * fps[n - i] / d |
|||
of fpsDeriv: |
|||
result = fps.s1[n + 1] * (n + 1) |
|||
of fpsInteg: |
|||
result = if n > 0: fps.s1[n - 1] / n else: fps.a0 |
|||
fps.cache[n] = result |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `$`*(fps: Fps): string = |
|||
## Return the representation of a FPS. |
|||
var c = fps[0] |
|||
if c != Zero: result &= $c |
|||
for i in 1..<DispTerm: |
|||
c = fps[i] |
|||
if c != Zero: |
|||
if c > Zero: |
|||
if result.len > 0: result &= " + " |
|||
else: |
|||
result &= " - " |
|||
c = -c |
|||
result &= (if c == One: XVar else: $c & XVar) & exponent(i) |
|||
if result.len == 0: result &= '0' |
|||
result &= " + ..." |
|||
#——————————————————————————————————————————————————————————————————————————————————————————————————— |
|||
# Build cos, sin and tan. |
|||
var cos = newFps() |
|||
let sin = cos.integral() |
|||
let tan = sin / cos |
|||
cos.redefine(newFps(1) - sin.integral()) |
|||
echo "sin(x) = ", sin |
|||
echo "cos(x) = ", cos |
|||
echo "tan(x) = ", tan |
|||
# Check that derivative of sin is cos. |
|||
echo "derivative of sin(x) = ", sin.derivative() |
|||
# Build exp using recursion. |
|||
let exp = newFps() |
|||
exp.redefine(newFps(1) + exp.integral()) |
|||
echo "exp(x) = ", exp</lang> |
|||
{{out}} |
|||
<pre>sin(x) = x - 1/6x³ + 1/120x⁵ - 1/5040x⁷ + 1/362880x⁹ - 1/39916800x¹¹ + ... |
|||
cos(x) = 1 - 1/2x² + 1/24x⁴ - 1/720x⁶ + 1/40320x⁸ - 1/3628800x¹⁰ + ... |
|||
tan(x) = x + 1/3x³ + 2/15x⁵ + 17/315x⁷ + 62/2835x⁹ + 1382/155925x¹¹ + ... |
|||
derivative of sin(x) = 1 - 1/2x² + 1/24x⁴ - 1/720x⁶ + 1/40320x⁸ - 1/3628800x¹⁰ + ... |
|||
exp(x) = 1 + x + 1/2x² + 1/6x³ + 1/24x⁴ + 1/120x⁵ + 1/720x⁶ + 1/5040x⁷ + 1/40320x⁸ + 1/362880x⁹ + 1/3628800x¹⁰ + 1/39916800x¹¹ + ...</pre> |
|||
===Using closure functions=== |
|||
This version is largely inspired from Kotlin version even if the way to implement the algorithm is pretty different. |
|||
<lang Nim>import rationals, sequtils |
|||
type |
|||
Fraction = Rational[int] |
|||
# Function to compute coefficients. |
|||
CoeffFunc = proc(n: int): Fraction |
|||
# Formal power series. |
|||
Fps = ref object |
|||
cache: seq[Fraction] # Cache to store values. |
|||
coeffs: CoeffFunc # Function to compute coefficients. |
|||
const |
|||
Zero: Fraction = 0 // 1 |
|||
One: Fraction = 1 // 1 |
|||
XVar = "x" |
|||
DispTerm = 12 |
|||
Super: array['0'..'9', string] = ["⁰", "¹", "²", "³", "⁴", "⁵", "⁶", "⁷", "⁸", "⁹"] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `$`(fract: Fraction): string = |
|||
## Return the representation of a fraction without the denominator if it is equal to 1. |
|||
if fract.den == 1: $fract.num else: rationals.`$`(fract) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc exponent(n: Natural): string = |
|||
## Return the representation of an exponent using unicode superscript. |
|||
if n == 1: return "" |
|||
for d in $n: result.add(Super[d]) |
|||
#################################################################################################### |
|||
# FPS. |
|||
func newFps*(coeffs: CoeffFunc): Fps = |
|||
## Create a FPS using the given "coeffs" function. |
|||
Fps(coeffs: coeffs) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func newFps*(coeffs: seq[Fraction]): Fps = |
|||
## Create a FPS using a list of fractions to initialize coefficients. |
|||
Fps(coeffs: proc(n: int): Fraction = (if n in 0..coeffs.high: coeffs[n] else: Zero)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func newFps*(coeffs: seq[int]): Fps = |
|||
## Create a FPS using a list of integer values to initialize coefficients. |
|||
Fps(coeffs: proc(n: int): Fraction = (if n in 0..coeffs.high: coeffs[n] // 1 else: Zero)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
func copyFrom(dest, src: Fps) {.inline.} = |
|||
## Copy a FPS into another. |
|||
dest[] = src[] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `[]`*(fps: Fps; n: int): Fraction = |
|||
## Return the element of degree "n" from a FPS. |
|||
if n < 0: return Zero |
|||
for i in fps.cache.len..n: |
|||
fps.cache.add(fps.coeffs(i)) |
|||
result = fps.cache[n] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc inverseCoeff*(fps: FPS; n: int): Fraction = |
|||
## Return the inverse coefficient of coefficient of degree "n". |
|||
var res = repeat(Zero, n + 1) |
|||
res[0] = fps[0].reciprocal |
|||
for i in 1..n: |
|||
for j in 0..<i: res[i] += fps[i - j] * res[j] |
|||
res[i] *= -res[0] |
|||
result = res[n] |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `+`*(a, b: Fps): Fps = |
|||
## Build the FPS sum of two FPS. |
|||
Fps(coeffs: proc(n: int): Fraction = a[n] + b[n]) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `-`*(a, b: Fps): Fps = |
|||
## Build the FPS difference of two FPS. |
|||
Fps(coeffs: proc(n: int): Fraction = a[n] - b[n]) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `*`*(a, b: Fps): Fps = |
|||
## Build the FPS product of two FPS. |
|||
Fps(coeffs: proc(n: int): Fraction = |
|||
result = Zero |
|||
for i in 0..n: result += a[i] * b[n - i]) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `/`*(a, b: Fps): Fps = |
|||
## Build the FPS quotient of two FPS. |
|||
Fps(coeffs: proc(n: int): Fraction = |
|||
result = Zero |
|||
for i in 0..n: result += a[i] * b.inverseCoeff(n - i)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc derivative*(fps: Fps): Fps = |
|||
## Build the FPS derivative of a FPS. |
|||
Fps(coeffs: proc(n: int): Fraction = fps[n + 1] * (n + 1)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc integral*(fps: Fps): Fps = |
|||
## Build the FPS integral of a FPS. |
|||
Fps(coeffs: proc(n: int): Fraction = (if n == 0: Zero else: fps[n - 1] / n)) |
|||
#--------------------------------------------------------------------------------------------------- |
|||
proc `$`*(fps: Fps): string = |
|||
## Return the representation of a FPS. |
|||
var c = fps[0] |
|||
if c != Zero: result &= $c |
|||
for i in 1..<DispTerm: |
|||
c = fps[i] |
|||
if c != Zero: |
|||
if c > Zero: |
|||
if result.len > 0: result &= " + " |
|||
else: |
|||
result &= " - " |
|||
c = -c |
|||
result &= (if c == One: XVar else: $c & XVar) & exponent(i) |
|||
if result.len == 0: result &= '0' |
|||
result &= " + ..." |
|||
#——————————————————————————————————————————————————————————————————————————————————————————————————— |
|||
# Build cos, sin and tan. |
|||
var cos = Fps() |
|||
let sin = cos.integral() |
|||
cos.copyFrom(newFps(@[1]) - sin.integral()) |
|||
let tan = sin / cos |
|||
echo "sin(x) = ", sin |
|||
echo "cos(x) = ", cos |
|||
echo "tan(x) = ", tan |
|||
# Check that derivative of sin is cos. |
|||
echo "derivative of sin(x) = ", sin.derivative() |
|||
# Build exp using recursion. |
|||
let exp = Fps() |
|||
exp.copyFrom(newFps(@[1]) + exp.integral()) |
|||
echo "exp(x) = ", exp</lang> |
|||
{{out}} |
|||
Same as with the other version. |
|||
=={{header|PARI/GP}}== |
=={{header|PARI/GP}}== |