Module `0x1::math128`

Standard math utilities missing in the Move Language.

Constants
Function max
Function min
Function average
Function gcd
Function lcm
Function mul_div
Function clamp
Function pow
Function floor_log2
Function log2
Function log2_64
Function sqrt
Function ceil_div
Specification

<pre><code>use <a href="../../move-stdlib/doc/fixed_point32.md#0x1_fixed_point32">0x1::fixed_point32</a>; use <a href="fixed_point64.md#0x1_fixed_point64">0x1::fixed_point64</a>; </code></pre>

Constants

Cannot log2 the value 0

<pre><code>const <a href="math128.md#0x1_math128_EINVALID_ARG_FLOOR_LOG2">EINVALID_ARG_FLOOR_LOG2</a>: u64 = 1; </code></pre>

Function `max`

Return the largest of two numbers.

<pre><code>public fun <a href="math128.md#0x1_math128_max">max</a>(a: u128, b: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_max">max</a>(a: u128, b: u128): u128 { if (a >= b) a else b } </code></pre> </details>

Function `min`

Return the smallest of two numbers.

<pre><code>public fun min(a: u128, b: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun min(a: u128, b: u128): u128 { if (a < b) a else b } </code></pre> </details>

Function `average`

Return the average of two.

<pre><code>public fun <a href="math128.md#0x1_math128_average">average</a>(a: u128, b: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_average">average</a>(a: u128, b: u128): u128 { if (a < b) { a + (b - a) / 2 } else { b + (a - b) / 2 } } </code></pre> </details>

Function `gcd`

Return greatest common divisor of <code>a</code> & <code>b</code>, via the Euclidean algorithm.

<pre><code>public fun <a href="math128.md#0x1_math128_gcd">gcd</a>(a: u128, b: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public inline fun <a href="math128.md#0x1_math128_gcd">gcd</a>(a: u128, b: u128): u128 { let (large, small) = if (a > b) (a, b) else (b, a); while (small != 0) { let tmp = small; small = large % small; large = tmp; }; large } </code></pre> </details>

Function `lcm`

Return least common multiple of <code>a</code> & <code>b</code>

<pre><code>public fun <a href="math128.md#0x1_math128_lcm">lcm</a>(a: u128, b: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public inline fun <a href="math128.md#0x1_math128_lcm">lcm</a>(a: u128, b: u128): u128 { if (a == 0 || b == 0) { 0 } else { a / <a href="math128.md#0x1_math128_gcd">gcd</a>(a, b) * b } } </code></pre> </details>

Function `mul_div`

Returns a * b / c going through u256 to prevent intermediate overflow

<pre><code>public fun <a href="math128.md#0x1_math128_mul_div">mul_div</a>(a: u128, b: u128, c: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public inline fun <a href="math128.md#0x1_math128_mul_div">mul_div</a>(a: u128, b: u128, c: u128): u128 { // Inline functions cannot take constants, as then every module using it needs the constant assert!(c != 0, std::error::invalid_argument(4)); (((a as u256) * (b as u256) / (c as u256)) as u128) } </code></pre> </details>

Function `clamp`

Return x clamped to the interval [lower, upper].

<pre><code>public fun <a href="math128.md#0x1_math128_clamp">clamp</a>(x: u128, lower: u128, upper: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_clamp">clamp</a>(x: u128, lower: u128, upper: u128): u128 { min(upper, <a href="math128.md#0x1_math128_max">max</a>(lower, x)) } </code></pre> </details>

Function `pow`

Return the value of n raised to power e

<pre><code>public fun <a href="math128.md#0x1_math128_pow">pow</a>(n: u128, e: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_pow">pow</a>(n: u128, e: u128): u128 { if (e == 0) { 1 } else { let p = 1; while (e > 1) { if (e % 2 == 1) { p *= n; }; e /= 2; n *= n; }; p * n } } </code></pre> </details>

Function `floor_log2`

Returns floor(log2(x))

<pre><code>public fun <a href="math128.md#0x1_math128_floor_log2">floor_log2</a>(x: u128): u8 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_floor_log2">floor_log2</a>(x: u128): u8 { let res = 0; assert!(x != 0, std::error::invalid_argument(<a href="math128.md#0x1_math128_EINVALID_ARG_FLOOR_LOG2">EINVALID_ARG_FLOOR_LOG2</a>)); // Effectively the position of the most significant set bit let n = 64; while (n > 0) { if (x >= (1 << n)) { x >>= n; res += n; }; n >>= 1; }; res } </code></pre> </details>

Function `log2`

<pre><code>public fun <a href="math128.md#0x1_math128_log2">log2</a>(x: u128): <a href="../../move-stdlib/doc/fixed_point32.md#0x1_fixed_point32_FixedPoint32">fixed_point32::FixedPoint32</a> </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_log2">log2</a>(x: u128): FixedPoint32 { let integer_part = <a href="math128.md#0x1_math128_floor_log2">floor_log2</a>(x); // Normalize x to [1, 2) in fixed point 32. if (x >= 1 << 32) { x >>= (integer_part - 32); } else { x <<= (32 - integer_part); }; let frac = 0; let delta = 1 << 31; while (delta != 0) { // log x = 1/2 log x^2 // x in [1, 2) x = (x * x) >> 32; // x is now in [1, 4) // if x in [2, 4) then log x = 1 + log (x / 2) if (x >= (2 << 32)) { frac += delta; x >>= 1; }; delta >>= 1; }; <a href="../../move-stdlib/doc/fixed_point32.md#0x1_fixed_point32_create_from_raw_value">fixed_point32::create_from_raw_value</a> (((integer_part as u64) << 32) + frac) } </code></pre> </details>

Function `log2_64`

<pre><code>public fun <a href="math128.md#0x1_math128_log2_64">log2_64</a>(x: u128): <a href="fixed_point64.md#0x1_fixed_point64_FixedPoint64">fixed_point64::FixedPoint64</a> </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_log2_64">log2_64</a>(x: u128): FixedPoint64 { let integer_part = <a href="math128.md#0x1_math128_floor_log2">floor_log2</a>(x); // Normalize x to [1, 2) in fixed point 63. To ensure x is smaller then 1<<64 if (x >= 1 << 63) { x >>= (integer_part - 63); } else { x <<= (63 - integer_part); }; let frac = 0; let delta = 1 << 63; while (delta != 0) { // log x = 1/2 log x^2 // x in [1, 2) x = (x * x) >> 63; // x is now in [1, 4) // if x in [2, 4) then log x = 1 + log (x / 2) if (x >= (2 << 63)) { frac += delta; x >>= 1; }; delta >>= 1; }; <a href="fixed_point64.md#0x1_fixed_point64_create_from_raw_value">fixed_point64::create_from_raw_value</a> (((integer_part as u128) << 64) + frac) } </code></pre> </details>

Function `sqrt`

Returns square root of x, precisely floor(sqrt(x))

<pre><code>public fun <a href="math128.md#0x1_math128_sqrt">sqrt</a>(x: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public fun <a href="math128.md#0x1_math128_sqrt">sqrt</a>(x: u128): u128 { if (x == 0) return 0; // Note the plus 1 in the expression. Let n = floor_lg2(x) we have x in [2^n, 2^{n+1}) and thus the answer in // the half-open interval [2^(n/2), 2^{(n+1)/2}). For even n we can write this as [2^(n/2), <a href="math128.md#0x1_math128_sqrt">sqrt</a>(2) 2^{n/2}) // for odd n [2^((n+1)/2)/<a href="math128.md#0x1_math128_sqrt">sqrt</a>(2), 2^((n+1)/2). For even n the left end point is integer for odd the right // end point is integer. If we choose as our first approximation the integer end point we have as maximum // relative <a href="../../move-stdlib/doc/error.md#0x1_error">error</a> either (<a href="math128.md#0x1_math128_sqrt">sqrt</a>(2) - 1) or (1 - 1/<a href="math128.md#0x1_math128_sqrt">sqrt</a>(2)) both are smaller then 1/2. let res = 1 << ((<a href="math128.md#0x1_math128_floor_log2">floor_log2</a>(x) + 1) >> 1); // We use standard newton-rhapson iteration to improve the initial approximation. // The <a href="../../move-stdlib/doc/error.md#0x1_error">error</a> term evolves as delta_i+1 = delta_i^2 / 2 (quadratic convergence). // It turns out that after 5 iterations the delta is smaller than 2^-64 and thus below the treshold. res = (res + x / res) >> 1; res = (res + x / res) >> 1; res = (res + x / res) >> 1; res = (res + x / res) >> 1; res = (res + x / res) >> 1; min(res, x / res) } </code></pre> </details>

Function `ceil_div`

<pre><code>public fun <a href="math128.md#0x1_math128_ceil_div">ceil_div</a>(x: u128, y: u128): u128 </code></pre> <details> <summary>Implementation</summary> <pre><code>public inline fun <a href="math128.md#0x1_math128_ceil_div">ceil_div</a>(x: u128, y: u128): u128 { // <a href="math128.md#0x1_math128_ceil_div">ceil_div</a>(x, y) = floor((x + y - 1) / y) = floor((x - 1) / y) + 1 // (x + y - 1) could spuriously overflow. so we use the later version if (x == 0) { // Inline functions cannot take constants, as then every module using it needs the constant assert!(y != 0, std::error::invalid_argument(4)); 0 } else (x - 1) / y + 1 } </code></pre> </details>

Specification

Function `max`

<pre><code>public fun <a href="math128.md#0x1_math128_max">max</a>(a: u128, b: u128): u128 </code></pre> <pre><code>aborts_if false; ensures a >= b ==> result == a; ensures a result == b; </code></pre>

Function `min`

<pre><code>public fun min(a: u128, b: u128): u128 </code></pre> <pre><code>aborts_if false; ensures a result == a; ensures a >= b ==> result == b; </code></pre>

Function `average`

<pre><code>public fun <a href="math128.md#0x1_math128_average">average</a>(a: u128, b: u128): u128 </code></pre> <pre><code>pragma opaque; aborts_if false; ensures result == (a + b) / 2; </code></pre>

Function `clamp`

<pre><code>public fun <a href="math128.md#0x1_math128_clamp">clamp</a>(x: u128, lower: u128, upper: u128): u128 </code></pre> <pre><code>requires (lower <= upper); aborts_if false; ensures (lower <=x && x <= upper) ==> result == x; ensures (x < lower) ==> result == lower; ensures (upper < x) ==> result == upper; </code></pre>

Function `pow`

<pre><code>public fun <a href="math128.md#0x1_math128_pow">pow</a>(n: u128, e: u128): u128 </code></pre> <pre><code>pragma opaque; aborts_if [abstract] <a href="math128.md#0x1_math128_spec_pow">spec_pow</a>(n, e) > MAX_U128; ensures [abstract] result == <a href="math128.md#0x1_math128_spec_pow">spec_pow</a>(n, e); </code></pre>

Function `floor_log2`

<pre><code>public fun <a href="math128.md#0x1_math128_floor_log2">floor_log2</a>(x: u128): u8 </code></pre> <pre><code>pragma opaque; aborts_if [abstract] x == 0; ensures [abstract] <a href="math128.md#0x1_math128_spec_pow">spec_pow</a>(2, result) <= x; ensures [abstract] x < <a href="math128.md#0x1_math128_spec_pow">spec_pow</a>(2, result+1); </code></pre>

Function `sqrt`

<pre><code>public fun <a href="math128.md#0x1_math128_sqrt">sqrt</a>(x: u128): u128 </code></pre> <pre><code>pragma opaque; aborts_if [abstract] false; ensures [abstract] x > 0 ==> result * result <= x; ensures [abstract] x > 0 ==> x < (result+1) * (result+1); </code></pre>

Module `0x1::math128`

Module 0x1::math128

Constants

Function max

Function min

Function average

Function gcd

Function lcm

Function mul_div

Function clamp

Function pow

Function floor_log2

Function log2

Function log2_64

Function sqrt

Function ceil_div

Specification

Function max

Function min

Function average

Function clamp

Function pow

Function floor_log2

Function sqrt

Module `0x1::math128`

Function `max`

Function `min`

Function `average`

Function `gcd`

Function `lcm`

Function `mul_div`

Function `clamp`

Function `pow`

Function `floor_log2`

Function `log2`

Function `log2_64`

Function `sqrt`

Function `ceil_div`

Function `max`

Function `min`

Function `average`

Function `clamp`

Function `pow`

Function `floor_log2`

Function `sqrt`