How to resolve the algorithm Faulhaber's triangle step by step in the Ruby programming language
How to resolve the algorithm Faulhaber's triangle step by step in the Ruby programming language
Table of Contents
Problem Statement
Named after Johann Faulhaber, the rows of Faulhaber's triangle are the coefficients of polynomials that represent sums of integer powers, which are extracted from Faulhaber's formula:
where
B
n
{\displaystyle B_{n}}
is the nth-Bernoulli number.
The first 5 rows of Faulhaber's triangle, are:
Using the third row of the triangle, we have:
∑
k
1
n
k
2
=
1 6
n +
1 2
n
2
1 3
n
3
{\displaystyle \sum _{k=1}^{n}k^{2}={1 \over 6}n+{1 \over 2}n^{2}+{1 \over 3}n^{3}}
Let's start with the solution:
Step by Step solution about How to resolve the algorithm Faulhaber's triangle step by step in the Ruby programming language
The provided Ruby code implements a program to calculate and display the coefficients of Faulhaber's triangle up to a specified order. Faulhaber's triangle is a triangular array of numbers that represent the sums of powers of natural numbers. It is useful for approximating certain mathematical functions.
Here's a breakdown of the code:
-
Frac Class:
- The
Frac
class represents rational numbers as fractions. It has instance variables@num
and@denom
to store the numerator and denominator, respectively. - It provides methods for arithmetic operations like addition (
+
), subtraction (-
), and multiplication (*
). - It also defines a
to_s
method to convert the fraction to a string representation.
- The
-
Constants:
FRAC_ZERO
andFRAC_ONE
are constants representing fractions 0/1 and 1/1, respectively.
-
Bernoulli Function:
- The
bernoulli
function calculates then
-th Bernoulli number using the explicit formula. It first initializes an arraya
of sizen+1
, with the first element set toFRAC_ZERO
. - It then iterates through each element
m
in the array and calculatesa[m]
based on the formula:a[m] = 1 / (m + 1) - Σ{j=1..m} a[j - 1] * j / 1
- The result of the function is
a[0]
ifn
is not equal to 1, or-a[0]
ifn
is equal to 1.
- The
-
Binomial Function:
- The
binomial
function calculates the binomial coefficientC(n, k)
using the formula:C(n, k) = n! / (k! * (n - k)!)
- It does this by computing the numerator and denominator separately and performing integer division.
- The
-
Faulhaber Triangle Function:
- The
faulhaberTriangle
function calculates the coefficients of Faulhaber's triangle up to a given orderp
. It initializes an arraycoeffs
of sizep+1
with the first element set toFRAC_ZERO
. - It then iterates through each element
j
from 0 top
and calculates the coefficients as follows:
wherecoeffs[p - j] = (-1)^j * (1 / (p + 1)) * C(p + 1, j) * B(j)
B(j)
is thej
-th Bernoulli number computed using thebernoulli
function.
- The
-
Main Function:
- The
main
function serves as the entry point of the program. It calculates and displays the coefficients of Faulhaber's triangle for orders 0 to 9.
- The
-
Program Flow:
- The program starts by invoking the
main
function. - The
main
function calls thefaulhaberTriangle
function for each order from 0 to 9. - The coefficients for each order are printed using the
to_s
method of theFrac
class.
- The program starts by invoking the
Source code in the ruby programming language
class Frac
attr_accessor:num
attr_accessor:denom
def initialize(n,d)
if d == 0 then
raise ArgumentError.new('d cannot be zero')
end
nn = n
dd = d
if nn == 0 then
dd = 1
elsif dd < 0 then
nn = -nn
dd = -dd
end
g = nn.abs.gcd(dd.abs)
if g > 1 then
nn = nn / g
dd = dd / g
end
@num = nn
@denom = dd
end
def to_s
if self.denom == 1 then
return self.num.to_s
else
return "%d/%d" % [self.num, self.denom]
end
end
def -@
return Frac.new(-self.num, self.denom)
end
def +(rhs)
return Frac.new(self.num * rhs.denom + self.denom * rhs.num, rhs.denom * self.denom)
end
def -(rhs)
return Frac.new(self.num * rhs.denom - self.denom * rhs.num, rhs.denom * self.denom)
end
def *(rhs)
return Frac.new(self.num * rhs.num, rhs.denom * self.denom)
end
end
FRAC_ZERO = Frac.new(0, 1)
FRAC_ONE = Frac.new(1, 1)
def bernoulli(n)
if n < 0 then
raise ArgumentError.new('n cannot be negative')
end
a = Array.new(n + 1)
a[0] = FRAC_ZERO
for m in 0 .. n do
a[m] = Frac.new(1, m + 1)
m.downto(1) do |j|
a[j - 1] = (a[j - 1] - a[j]) * Frac.new(j, 1)
end
end
if n != 1 then
return a[0]
end
return -a[0]
end
def binomial(n, k)
if n < 0 then
raise ArgumentError.new('n cannot be negative')
end
if k < 0 then
raise ArgumentError.new('k cannot be negative')
end
if n < k then
raise ArgumentError.new('n cannot be less than k')
end
if n == 0 or k == 0 then
return 1
end
num = 1
for i in k + 1 .. n do
num = num * i
end
den = 1
for i in 2 .. n - k do
den = den * i
end
return num / den
end
def faulhaberTriangle(p)
coeffs = Array.new(p + 1)
coeffs[0] = FRAC_ZERO
q = Frac.new(1, p + 1)
sign = -1
for j in 0 .. p do
sign = -sign
coeffs[p - j] = q * Frac.new(sign, 1) * Frac.new(binomial(p + 1, j), 1) * bernoulli(j)
end
return coeffs
end
def main
for i in 0 .. 9 do
coeffs = faulhaberTriangle(i)
coeffs.each do |coeff|
print "%5s " % [coeff]
end
puts
end
end
main()
You may also check:How to resolve the algorithm Sorting algorithms/Selection sort step by step in the C programming language
You may also check:How to resolve the algorithm Number reversal game step by step in the D programming language
You may also check:How to resolve the algorithm Sort three variables step by step in the Ada programming language
You may also check:How to resolve the algorithm Arrays step by step in the LSL programming language
You may also check:How to resolve the algorithm Primes - allocate descendants to their ancestors step by step in the Nim programming language