# Intro

* Basic Number Theory Every Programmer Should Know...by CodeChef
* Quora : What important topics of number theory should every programmer know?
* science4all : numbers-and-constructibility
* Number Theory
* How Computers Use Numbers by Mabi19

# Number types

Number can be used as :
* a numerical values used in numerical computations
* a symbols used in symbolic computations
Number ( for example angle in turns ) can be:
* decimal number (base = 10 )
** integer
** real number
*** ratio = fraction ( Finite continued fraction ) = rational number ( the irrationality measure of any rational number is 1)
**** in lowest terms ( irreducible form ) : ${\tfrac {1}{21}}$
**** reducible form
***** in explicit normalized form ( only when denominator is odd ): ${\tfrac {3}{63}}={\tfrac {3}{2^{6}-1}}$
*** irrational number = infinite continued fraction ( if number can not be represented as a ratio then it is irrational number )
**** algebraic ( irrationality measure = 2)
**** transcendental ( irrationality measure > 2)
** decimal floating point number $0.{\overline {047619}}$
*** finite expansion
*** infinite (endless) expansion
**** continue infinitely without repeating (in which case the number is called irrational = non-repeating non-terminating decimal numbers)
**** Recurring or repeating
***** (strictly) periodic ( preperiod = 0 , period > 0 )
***** mixed = eventually periodic ( preperiod > 0 , period > 0 )
* binary number ( base = 2 )
** binary rational number ( ratio) ${\tfrac {1}{10101}}$
** binary real number
*** binary floating point number ( scientific notation )
*** Raw binary ( raw IEEE format )
*** binary fixed point number ( notation)
**** with repeating sequences : $0.{\overline {000011}}$
**** with endless expansion $0.000011000011000011000011...$

## dimension

* 1D: real
* 2D
** dual
** complex
* 4D
** quaterions

## way to represent real numbers using a finite number of bits

* IEEE floating point
* fixed point
* unums (universal numbers) by John Gustafson
** Posits are a hardware-friendly version of unums

## expansion/representation

* finite = terminating
* infinite = non-terminating
** periodic = infite repeating
** preperiodic = eventually periodic
** non-periodic: binary numerals which neither terminate nor recur represent irrational numbers

## base

radix or base of a positional numeral system
* 2 ( binary number)
* 8 ( octal number)
* 10 ( decimal umber)
* 16 ( hexadecimal)

## form/notation

Notation
* sequence of digits and radix
** infinite sequence
*** in general form is denoted by ellipsis ( = 3 dots): $r=d_{0}.d_{1}d_{2}d_{3}\dots$
*** Infinitely repeating part of expansion denoted by
**** round brackets : $0.10(00101010)=0.10001010100010101000101010001010100010101000101010\dots$.
**** overline: $0.10{\overline {00101010}}=0.10001010100010101000101010001010100010101000101010\dots$
** finite sequence
*** 1.23
**** with trailing zeros: 1.2300 for indicating the number of significant figures, for example in a measurement.
*** with absolute measurment error: mean ± range, for example: 72.20 ± 0.02
* ratio of integers $r={\frac {m}{n}}$
** in lowest terms ( irreducible form ) : ${\tfrac {1}{21}}$
** reducible form
*** in explicit normalized form ( only when denominator is odd ):${\frac {n}{2^{p}-1}}$, for example : ${\tfrac {3}{63}}={\tfrac {3}{2^{6}-1}}$
*** The explicit normalized form of formula for denominator of angle : ${\frac {n}{(2^{p}-1)*2^{k}}}$
* continued fraction : $[a_{0};a_{1},a_{2},a_{3}]$
* scientific (exponential) form or notation:
    $6.022e23=6.022*10^{23}$
    $1.2345e-3=1.2345+10^{-3}$
    ${\tfrac {3}{63}}={\tfrac {3}{2^{6}-1}}={\tfrac {1}{21}}=0.04761904761904762$
A computer number formats ( storage forms)
* floating point form ( expansion) : the number's radix point can "float" anywhere to the left, right, or between the significant digits of the number.
* fixed point format

### Round brackets

brackets with exponent ( superscript) denotes how many times the series repeats
    $0.11(11101010)=0.11(11(10)^{3})$

### Trailing zeros

Trailing zeros to the right of a decimal point, as in 12.3400, do not affect the value of a number and may be omitted if all that is of interest is its numerical value. This is true even if the zeros recur infinitely. For example, in pharmacy, trailing zeros are omitted from dose values to prevent misreading. However, trailing zeros may be useful for indicating the number of significant figures, for example in a measurement. In such a context, "simplifying" a number by removing trailing zeros would be incorrect.
The number of trailing zeros in a non-zero base-b integer n equals the exponent of the highest power of b that divides n. For example, 14000 has three trailing zeros and is therefore divisible by 1000 = 103, but not by 104. This property is useful when looking for small factors in integer factorization. Some computer architectures have a count trailing zeros operation in their instruction set for efficiently determining the number of trailing zero bits in a machine word.

# Examples of binary expansions

First check if the ratio is in the lowest terms ( reducible)
Binary expansion can be :
* finite
* infinite
** periodic : preperiod = 0, period > 0
** preperiodic ( = eventually periodic) : preperiod > 0, period > 0
** aperiodic : preperiod = 0, period = 0

# Conversions

Conversion between :
* bases ( from binary to decimal, ...)
* forms ( rational to expansion, ...)
** Recognizing Rational Numbers From Their Decimal Expansion: "to compute the simple continued fraction of the approximation, and truncate it before a large partial quotient a_n, then compute the value of the truncated continued fraction."
** converting-repeating-decimals-to-fractions
** fraction to recurring decimal
*** use of Floyd's Cycle Detection Algorithm for finding of the first repetitive remainder
*** recursive division and collection of remainders (associated with pieces of decimal fraction)
** convert-repeating-fractions-to-different-bases
Using :
* online calculators
* code

## Algorithms

* Find
** strictly repeating patterns (that you do not know in advance) in a binary string/sequence "If there is a pattern => its length must divide the string length "AnotherGeek
*** using regex
*** javascript
** non-repeating and strictly repeating patterns (that you do not know in advance) in a binary string/sequence
* convert a number with a repeating fractional part

### Reducing Fractions to Lowest Terms

A fraction that is reducible can be reduced by dividing both the numerator and denominator by a common factor. It can be fully reduced to lowest terms if both are divided by their greatest common divisor
Algorithms for finding the greatest common divisor:
* the Euclidean algorithm
* prime factorization
The Euclidean algorithm is commonly preferred because it allows one to reduce fractions with numerators and denominators too large to be easily factored
Examples:
* desmos: graphical fraction reduction

### convert decimal fraction to binary

"... we repeatedly multiply the decimal fraction by 2. If the result is greater than or equal to 1, we add a 1 to our answer. If the result is less than 1, we add a 0 to our answer." (from Virginia Tech Online CS module)
Algorithm:
* Multiply the input decimal fraction by two
* from above result
** take integer part as the binary digit
** take the fractional part as the starting point for the next step
* repeat until you either get to 0 or a periodic number
* read the number starting from the top - the first binary digit is the first digit after the comma
Example of conversion 0.1 decimal fraction to binary fraction :
Result:
Repeating fractions :
Code
* geeksforgeeks: convert-decimal-fraction-binary-number
* primary-bulb by Claude Heiland-Allen

### Convert binary fraction to decimal ratio
#### Geometric series

(Pre)periodic binary fraction can be split into 2 fractions:
* finite
* infinite: periodic with empty or filled with zeros preperiodic part
    $0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{p})=0.\overbrace {b...b} ^{t}+0.\overbrace {0...0} ^{t}(\overbrace {b...b} ^{p})$
Formula for the geometric series when |r|<1 :
$a+ar+ar^{2}+ar^{3}+ar^{4}+\cdots =\sum _{k=0}^{\infty }ar^{k}={\frac {a}{1-r}}$
For the infinite periodic binary fraction with empty or filled with zeros preperiodic part this formula is
    $0.\overbrace {0...0} ^{t}(\overbrace {b...b} ^{p})={\frac {a}{1-r}}$
where :
* b is a binary digit : 0 or 1
* t is a length of preperiodic block
* p is a length of the periodic block
* the value of a is simply the value of the first occurrence of the repeating block $a=0.\overbrace {0...0} ^{t}\overbrace {b...b} ^{p}$
* the value of $r={\frac {1}{2^{p}}}$ so $1-r={\frac {2^{p}-1}{2^{p}}}$
    $0.\overbrace {b...b} ^{t}(\overbrace {b...b} ^{p})=0.\overbrace {b...b} ^{t}+{\frac {a}{1-r}}=0.\overbrace {b...b} ^{t}+{\frac {0.\overbrace {0...0} ^{t}\overbrace {b...b} ^{p}}{\frac {2^{p}-1}{2^{p}}}}$
Full formula is now:
Examples :
* $0.(0011)={\frac {0.0011}{\frac {2^{4}-1}{2^{4}}}}={\frac {3/16}{15/16}}={\frac {1}{5}}$
* $0.00(0011)={\frac {0.000011}{\frac {2^{4}-1}{2^{4}}}}={\frac {3/64}{15/16}}={\frac {1}{20}}$
* $0.01(1100)=0.01+{\frac {0.0011}{\frac {2^{4}-1}{2^{4}}}}={\frac {1}{4}}+{\frac {3/16}{15/16}}={\frac {1}{4}}+{\frac {1}{5}}={\frac {9}{20}}$
$0.0101(11001)=0.0101+{\frac {0.000011001}{\frac {2^{5}-1}{2^{5}}}}={\frac {5}{16}}+{\frac {25/512}{31/32}}={\frac {5}{16}}+{\frac {25}{496}}={\frac {45}{124}}$

## code examples
### bc

Conversion from decimal ratio to binary using bc – arbitrary–precision arithmetic language

### C

* itoa
* snprintf
* Binary integer constant
* Macro BOOST_BINARY
* gmp
* mandelbrot-symbolics lbrary by Claude Heiland-Allen
** Fractals/mandelbrot-symbolics#m-binangle-from-rational binangle-from-rational
* Conversion numbers to binary representation by Wojciech Muła

#### itoa

itoa function

#### Binary integer constant

Binary integer constant
"Integer constants can be written as binary constants, consisting of a sequence of ‘0’ and ‘1’ digits, prefixed by ‘0b’ or ‘0B’. This is particularly useful in environments that operate a lot on the bit level (like microcontrollers).
The following statements are identical:
The type of these constants follows the same rules as for octal or hexadecimal integer constants, so suffixes like ‘L’ or ‘UL’ can be applied."

#### gmp

GMP library
Output :

### Haskell

Code by Claude Heiland-Allen:

### Python

Other methods

# How to use numbers in computer programs ?

First read:
* article "What Every Computer Scientist Should Know About Floating-Point Arithmetic" by DAVID GOLDBERG :
* Josh HabermanFloating Point Demystified, Part 1 by
* floating-point-demystified-part2

## integer

* types
* limits and overflow

### Limit

Results :
For example Wolf Jung in program Mandel makes a silent bounds check:
If r is to big for unsigned long long int type it returns 0 to prevent ineger overflow.
GMP library has arbitrary precision rationals.

## floating point
### precision

Precision
* GMP : The mantissa of each float has a user-selectable precision ( variable prec type mp_bitcnt_t ). Counts of bits of a multi-precision number are represented in the C type mp_bitcnt_t. Currently this is always an unsigned long
* MPFR : The precision is the number of bits used to represent the significand ( mantissa) of a floating-point number; the corresponding C data type is mpfr_prec_t.

## Rational

"Any number with a finite decimal expansion is a rational number. " In other words : "any floating point number can be converted to a rational number."
So in numerical computations one can use only integer of floating points numbers ( rational ).

### Binary

* Exploring Binary Numbers With PARI/GP Calculator By Rick Regan
* Wolfram Alpha

#### Numbers

In C one can use :
* bitwise operators
In Maxima CAS one can use :

#### String

Calculation of binary numbers with as a string with replicating parts in Haskell (ghci):
In Python :

#### Literal

In python one can use binary literals :

## Irrational = not rational

Expansion is non terminating and non repeating
Types:
* Algebraic Numbers = roots of Algebraic Equations. Examplle : sqrt(2),
* transcendental numbers = non algebraic
If one wants use irrational number then should check :
* symbolic computations :
** exact number can be used as a symbol, but "you cannot print the whole irrational number"
** infinite continued fraction
* numerical computations : close rational approximations to irrational numbers (the Diophantine Approximation)
** ratio of integers
** floating point number
** finite continued fractions

### Inverse golden mean

The most irrational number In a continued fraction all numbers are 1 = the slowest convergence of all the irrational numbers
Using Maxima CAS :
and :
where denominator :

## complex

* the multi-valued nature of complex powers can cause big troubles ( artifacts of branch cuts, arbitrary principal value of arg)
* domain coloring
Examples
* VBA
* Maxima CAS

## How to find number type

Note that in numerical computations with finite precision ( on computer) :
* if number is represented as a ratio ( of integers) then it is a rational number
* if number has a floating point representation the it is also a rational number because of limited precision = finite expansion

# tools

* dumpfp: A Tool to Inspect Floating-Point Numbers by Joshua Haberman
* float.exposed - and blog by Bartosz Ciechanowski

# More

* sequences
** orbits
*** period
* series
* cardinality
* partition
* random numbers

## Cardinality

In mathematic ( theory) :
* "... the rational numbers are a countable set whereas the irrational numbers are an uncountable set. In other words, there are more irrational numbers than there are rational. "
* "... in the set of real numbers there is continuum of irrational numbers and only aleph-zero rational numbers. Thus probability that any random number is irrational is 1;" ( Bartek Ogryczak) "To be pedantically correct you should have said almost certainly is 1. " – David Hammen

## height of a rational number in lowest term

Types of the height functions defined on the set of rational numbers $\mathbb {Q}$:
* $H(p/q)=\max\{|p|,|q|\}$ for the (multiplicative) height of a rational number also called naive height
* $h(p/q)=\log H(p/q)$ the logarithmic height or additive
where:
* p/q is a rational number in lowest term
Key words:
* number field
* Height Functions in Number Theory

## Paritition

* paritition function : "partition numbers behave like fractals, possessing an infinitely-repeating structure"

## Random number

The probability that any random number :
* is irrational is almost 1 ( in theory because of cardinality )
* is rational is 1 ( in numerical computations because of limited precision )

## Fields

* generalisation : scalar / vector / tensor
* fields : scalar , vector, tensor

# References

* ↑ exploring binary: nine-ways-to-display-a-floating-point-number
* ↑ wikipedia : Number base
* ↑ math.stackexchange question: are-there-real-numbers-that-are-neither-rational-nor-irrational
* ↑ HOW TO WORK WITH ONE-DI MENSIONAL QUADRATIC MAPS G. Pastor , M. Romera, G. Álvarez, and F. Montoya
* ↑ What Every Programmer Should Know About Floating-Point Arithmetic
* ↑ Stackoverflow : Why Are Floating Point Numbers Inaccurate?
* ↑ home school math : The fascinating irrational numbers
* ↑ Tutorial: Floating-Point Binary by Kip Irvine
* ↑ Dual Numbers & Automatic Differentiation
* ↑ videos: Imaginary Numbers are Real from Welch Labs
* ↑ math stackexchange question: is-there-a-third-dimension-of-numbers
* ↑ Beating Floating Point at its Own Game: Posit Arithmetic by John L. Gustafson , Isaac Yonemoto
* ↑ fractalforums.org : posits
* ↑ wikipedia: Radix
* ↑ Survey of Floating-Point Formats Robert Munafo's home pages on AWS   © 1996-2022 Robert P. Munafo.
* ↑ Physics 132 Lab Manual: how-to-write-numbers-significant-figures by Brokk Toggerson and Aidan Philbin
* ↑ HOW TO WORK WITH ONE-DI MENSIONAL QUADRATIC MAPS G. Pastor , M. Romera, G. Álvarez, and F. Montoya
* ↑ calculatorsoup: scientific-notation-converter
* ↑ A Method to Solve the Limitations in Drawing External Rays of the Mandelbrot Set M. Romera,1 G. Pastor, A. B. Orue,1 A. Martin, M.-F. Danca,and F. Montoya
* ↑ Converting fractions to strings of digits by Claude Heiland-Allen
* ↑ Rational Numbers From Their Decimal Expansion by William Stein
* ↑ basic-mathematics : converting-repeating-decimals-to-fractions
* ↑ Recurring decimal of a rational number by Yurii Lahodiuk
* ↑ quora : How-do-you-convert-repeating-fractions-to-different-bases
* ↑ knowledgedoor calculators: convert_a_ratio_of_integers
* ↑ R.Knott : Fractions – Decimals Calculator
* ↑ Base Number - Decimal Number Conversion
* ↑ Decimal to Floating-Point Converter By Rick Regan
* ↑ wolframalpha binary to decimal conversion
* ↑ stackoverflow question : best-algorithm-to-find-a-repeating-pattern
* ↑ stackoverflow questions : method-to-find-repeated-pattern-in-string-apart-from-regex?noredirect=1&lq=1
* ↑ stackoverflow question: finding-a-repeated-pattern-in-a-string
* ↑ stackoverflow question: finding-a-pattern-in-a-binary-string
* ↑ jsfiddle by Jan Turoń
* ↑ Virginia Tech Online CS module
* ↑ Stackoverflow : How do you convert a fraction to binary ?
* ↑ Converting a repeating binary number to decimal (express as a series?)
* ↑ wikipedia :Geometric_series
* ↑ stackoverflow question: converting-a-repeating-binary-number-to-decimal-express-as-a-series
* ↑ math.stackexchange question: find-a-fraction-given-the-repeating-binary-expansions
* ↑ Where is the itoa function in Linux?
* ↑ itoa with GCC by Stuart
* ↑ gcc - Binary-constants
* ↑ Programowanie_w_systemie_UNIX: GMP in polish wikibooks
* ↑ Converting fractions to strings of digits by Claude Heiland-Allen
* ↑ stackoverflow : python int to binary
* ↑ What Every Computer Scientist Should Know About Floating-Point Arithmetic by DAVID GOLDBERG
* ↑ wikipedia : Bounds checking
* ↑ stackoverflow questions : check-if-a-number-is-rational-in-python
* ↑ Joe McCullough : bitwise operators
* ↑ Stackoverflow : How do you express binary literals in Python?
* ↑ John D Cook : best-rational-approximation
* ↑ DISCOVERING EXACTLY WHEN A RATIONAL IS A BEST APPROXIMATE OF AN IRRATIONAL By KARI LOCK
* ↑ ams : The Most Irrational Number
* ↑ complex beauties : math-calendar
* ↑ David Bau : complex function viewer
* ↑ Complex Numbers in VBA by Pfadintegral
* ↑ dumpfp: A Tool to Inspect Floating-Point Numbers by Joshua Haberman
* ↑ home school math : The fascinating irrational numbers
* ↑ stackoverflow questions : irrational-number-check-function
* ↑ Introduction to Heights by Brian Lawrence
* ↑ sagemath : Rational.global_height
* ↑ Height Functions by Michael Tepper
* ↑ Fractal Structure to Partition Function.
* An Illustrated Theory of Numbers by Martin H. Weissman

# See also

* Divisor Plot : Explore composite number patterns
* Rational Points on the Unit Sphere: Approximation Complexity and Practical Constructions by Daniel Bahrdt, Martin P. Seybold
* Discrete Mathematics : Number representations
* A-level_Computing : Binary_fractions
* sequence_of_fraction_in_the_elephant_valley
* Fractals : Iterations_in_the_complex_plane , wake