# Numeric algorithms

#### sal/algo/numerics.h

modular_pow | modular exponentiation |

int_pow | integer exponentiation |

fibonacci | nth fibonacci number |

make_cyclic | create a cyclic number from 1/prime in given base |

cyclic_length | length of cyclic number from 1/prime in given base, 0 if acyclic |

is_pow | checks if guess is a power of base |

is_square | checks if number is a perfect square |

gcd | greatest common denominator (binary) |

gcd_euclidean | Euclidean algorithm for gcd |

gcd_alt | Another way for expressing the Euclidean algorithm |

totient | number of integers less than n that is relatively prime with n |

mul | matrix chain multiplication ordering |

factorize | prime factorization of smooth numbers |

factorize_rough | prime factorization of numbers with large prime factors |

num_factors | total number of factors (including composites) |

sum_factors | sum of all factors (including composites) |

### Exponentiation ¶

Declaration

Example

Discussion

The general approach is to exponentiate by squaring the base and
reducing the exponent to at most half each time. This gurantees completion
after `Θ(lg(exponent))`

computations.
Some more examples here.

### Fibonacci ¶

Declaration

Parameters

n | nth fibonacci number, sequence starting: (n=0)0, 1, 1.. |

Example

Discussion

Since exponentiation can be done in `Θ(lg(n))`

time,
expanding out clever matrices also shares that time complexity.
Because the fibonacci sequence can be defined recursively as a linear
combination of previous terms, such a matrix exists (the companion matrix), and is:

### Cyclic numbers ¶

Declaration

Parameters

base | number base |

prime | prime that does not divide base |

Example

Discussion

Cyclic numbers are related to repeating decimals, from which they can be generated in a given base b with prime p using the relation

They can be constructed by computing the digits of `1/p`

in base b
by long division and collecting the digits.

### Integer power ¶

Declaration

Example

Discussion

Through divisions, checks whether guess is an integer power of base.

### Perfect square ¶

Declaration

Example

Discussion

Used in tight loops of many number theory problems. Algorithm is written by maartinus from stackoverflow.

### Greatest Common Denominator ¶

Declaration

Parameters

a | integer (can be negative) |

b | integer (can be negative) |

Example

Discussion

Often used to solve combination problems. The binary optimization is used because gcd's common usage in time critical operations. The alternative versions are much simpler and easier to memorize.

### Euler's Totient ¶

Declaration

Parameters

n | number to find the totient of |

Example

Discussion

Number of positive integers less than n that is relatively prime to n.

`1 < k < n such that gcd(k,n) == 1`

It is multiplicative, so
`phi(a*b) == phi(a) * phi(b)`

One application is in Euler's theorem: that a and n are relatively prime iff

With applications here.

### Matrix Chain Multiplication ¶

Declaration

Example

Discussion

`Θ(n^3)`

work is done optimally parenthesize the multiplications using dynamic programming.
This order affects the number of operations required; using Wikipedia's example:

suppose A is a 10 × 30 matrix, B is a 30 × 5 matrix, and C is a 5 × 60 matrix. Then,

(AB)C = (10×30×5) + (10×5×60) = 1500 + 3000 = 4500 operations

A(BC) = (30×5×60) + (10×30×60) = 9000 + 18000 = 27000 operations.

### Integer Factorization ¶

Declaration

Example

Discussion

Factorizing in polynomial time is still an open problem.

Smooth numbers are ones that have small prime factors,
while rough numbers factor into large primes.
Trial division is used to factorize both, with the difference being
the divisor sequence for smooth numbers being that of odd numbers (2, 3, 5, 7, 9,...), while
rough numbers is that of generated primes (2, 3, 5, 7, 11,...). Trial division is very fast
for practical encounters.