libzahl

big integer library
git clone git://git.suckless.org/libzahl
Log | Files | Refs | README | LICENSE

commit 67ebaf88644f0bf47103af79fee76d015d43ce00
parent 7ad81d682ee7957bb87889e24138c37ed16db3d9
Author: Mattias Andrée <maandree@kth.se>
Date:   Sat, 23 Jul 2016 17:49:40 +0200

Add two exercises to the manual

[M10]  Convergence of the Lucas Number ratios
[M12+] Factorisation of factorials

Diffstat:
Makefile | 3++-
doc/exercises.tex | 96+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
doc/libzahl.tex | 2++
3 files changed, 100 insertions(+), 1 deletion(-)

diff --git a/Makefile b/Makefile @@ -82,7 +82,8 @@ TEXSRC =\ doc/bit-operations.tex\ doc/number-theory.tex\ doc/random-numbers.tex\ - doc/not-implemented.tex + doc/not-implemented.tex\ + doc/exercises.tex HDR_PUBLIC = zahl.h $(HDR_SEMIPUBLIC) HDR = $(HDR_PUBLIC) $(HDR_PRIVATE) diff --git a/doc/exercises.tex b/doc/exercises.tex @@ -0,0 +1,96 @@ +\chapter{Exercises} +\label{chap:Exercises} + +% TODO +% +% All exercises should be group with a chapter +% +% ▶ Recommended +% M Matematically oriented +% HM Higher matematical education required +% +% 00 Immediate +% 10 Simple +% 20 Medium +% 30 Moderately hard +% 40 Term project +% 50 Research project +% +% ⁺ High risk of undershoot difficulty + + +\begin{enumerate}[label=\textbf{\arabic*}.] + + +\item {[\textit{M10}]} \textbf{Convergence of the Lucas Number ratios} + +Find an approximation for $\displaystyle{ \lim_{n \to \infty} \frac{L_{n + 1}}{L_n}}$, +where $L_n$ is the $n^{\text{th}}$ Lucas Number \psecref{sec:Lucas numbers}. + +\( \displaystyle{ + L_n \stackrel{\text{\tiny{def}}}{\text{=}} \left \{ \begin{array}{ll} + 2 & \text{if} ~ n = 0 \\ + 1 & \text{if} ~ n = 1 \\ + L_{n - 1} + L_{n + 1} & \text{otherwise} + \end{array} \right . +}\) + + +\item {[\textit{M12${}^+$}]} \textbf{Factorisation of factorials} + +Implement the function + +\vspace{-1em} +\begin{alltt} + void factor_fact(z_t n); +\end{alltt} +\vspace{-1em} + +\noindent +which prints the prime factorisation of $n!$ (the $n^{\text{th}}$ factorial). +The function shall be efficient for all $n$ where all primes $p \le n$ can +be found efficiently. You can assume that $n \ge 2$. You should not evaluate $n!$. + + +\end{enumerate} + + + +\chapter{Solutions} +\label{chap:Solutions} + + +\begin{enumerate}[label=\textbf{\arabic*}.] + +\item \textbf{Convergence of the Lucas Number ratios} + +It would be a mistake to use bignum, and bigint in particular, +to solve this problem. Good old mathematics is a much better solution. + +$$ \lim_{n \to \infty} \frac{L_{n + 1}}{L_n} = \lim_{n \to \infty} \frac{L_{n}}{L_{n - 1}} = \lim_{n \to \infty} \frac{L_{n - 1}}{L_{n - 2}} $$ + +$$ \frac{L_{n}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ + +$$ \frac{L_{n - 1} + L_{n - 2}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ + +$$ 1 + \frac{L_{n - 2}}{L_{n - 1}} = \frac{L_{n - 1}}{L_{n - 2}} $$ + +$$ 1 + \varphi = \frac{1}{\varphi} $$ + +So the ratio tends toward the golden ration. + + +\item \textbf{Factorisation of factorials} + +Base your implementation on + +\( \displaystyle{ + n! = \prod_{p~\in~\textbf{P}}^{n} p^{k_p}, ~\text{where}~ + k_p = \sum_{a = 1}^{\lfloor \log_p n \rfloor} \lfloor np^{-a} \rfloor. +}\) + +There is no need to calculate $\lfloor \log_p n \rfloor$, +you will see when $p^a > n$. + + +\end{enumerate} diff --git a/doc/libzahl.tex b/doc/libzahl.tex @@ -6,6 +6,7 @@ \usepackage{amsmath, amssymb, mathtools, MnSymbol, mathrsfs, esvect} \usepackage{tipa, color, graphicx} \usepackage{shorttoc, minitoc} +\usepackage{enumitem} \usepackage[english]{babel} \selectlanguage{english} \definecolor{linkcolour}{RGB}{112, 0, 0} @@ -103,6 +104,7 @@ copyright notice and this permission notice appear in all copies.} \input doc/number-theory.tex \input doc/random-numbers.tex \input doc/not-implemented.tex +\input doc/exercises.tex \appendix