Skip to content

Commit

Permalink
Additions to Big arithmetics (#4653)
Browse files Browse the repository at this point in the history
* Additions to Big arithmetics.
Follows #4560.

* Follow @RX14 review (single line blocks, extract mantissa bits constants).

* Int cast is implicit here.

* Format src/big/big_rational.cr

* BigRational is not float, and frexp should be not used on it.

* frexp should not be used on BigInt.

* rework BigFloat./

* rename bsi, bfsi, bsf, bfsf etc. in spec.

* rework def BigFloat.<=>(other : Int)

* Simplify a bit, thanks to @RX14

* just remove commen. looks like single Number constructor looks OK in every case.

* more verbose naming for used variables.

* just explanation of workaround, refs #4897

* For now overloads work (i don't know why).

* dedup

* Forward declarations of Big Arithmentics types.
akzhan authored and RX14 committed Sep 1, 2017
1 parent 842548e commit d1960a5
Showing 8 changed files with 331 additions and 20 deletions.
72 changes: 72 additions & 0 deletions spec/std/big/big_float_spec.cr
Original file line number Diff line number Diff line change
@@ -2,6 +2,62 @@ require "spec"
require "big_float"

describe "BigFloat" do
describe "new" do
string_of_integer_value = "123456789012345678901"
bigfloat_of_integer_value = BigFloat.new(string_of_integer_value)
string_of_float_value = "1234567890.12345678901"
bigfloat_of_float_value = BigFloat.new(string_of_float_value)

it "new(String)" do
bigfloat_of_integer_value.to_s.should eq(string_of_integer_value)
bigfloat_of_float_value.to_s.should eq(string_of_float_value)
end

it "new(BigInt)" do
bigfloat_on_bigint_value = BigFloat.new(BigInt.new(string_of_integer_value))
bigfloat_on_bigint_value.should eq(bigfloat_of_integer_value)
bigfloat_on_bigint_value.to_s.should eq(string_of_integer_value)
end

it "new(BigRational)" do
bigfloat_on_bigrational_value = BigFloat.new(BigRational.new(1, 3))
bigfloat_on_bigrational_value.should eq(BigFloat.new(1) / BigFloat.new(3))
end

it "new(BigFloat)" do
BigFloat.new(bigfloat_of_integer_value).should eq(bigfloat_of_integer_value)
BigFloat.new(bigfloat_of_float_value).should eq(bigfloat_of_float_value)
end

it "new(Int)" do
BigFloat.new(1_u8).to_s.should eq("1")
BigFloat.new(1_u16).to_s.should eq("1")
BigFloat.new(1_u32).to_s.should eq("1")
BigFloat.new(1_u64).to_s.should eq("1")
BigFloat.new(1_i8).to_s.should eq("1")
BigFloat.new(1_i16).to_s.should eq("1")
BigFloat.new(1_i32).to_s.should eq("1")
BigFloat.new(1_i64).to_s.should eq("1")
BigFloat.new(-1_i8).to_s.should eq("-1")
BigFloat.new(-1_i16).to_s.should eq("-1")
BigFloat.new(-1_i32).to_s.should eq("-1")
BigFloat.new(-1_i64).to_s.should eq("-1")

BigFloat.new(255_u8).to_s.should eq("255")
BigFloat.new(65535_u16).to_s.should eq("65535")
BigFloat.new(4294967295_u32).to_s.should eq("4294967295")
BigFloat.new(18446744073709551615_u64).to_s.should eq("18446744073709551615")
BigFloat.new(127_i8).to_s.should eq("127")
BigFloat.new(32767_i16).to_s.should eq("32767")
BigFloat.new(2147483647_i32).to_s.should eq("2147483647")
BigFloat.new(9223372036854775807_i64).to_s.should eq("9223372036854775807")
BigFloat.new(-128_i8).to_s.should eq("-128")
BigFloat.new(-32768_i16).to_s.should eq("-32768")
BigFloat.new(-2147483648_i32).to_s.should eq("-2147483648")
BigFloat.new(-9223372036854775808_i64).to_s.should eq("-9223372036854775808")
end
end

describe "-@" do
bf = "0.12345".to_big_f
it { (-bf).to_s.should eq("-0.12345") }
@@ -40,6 +96,8 @@ describe "BigFloat" do
it { ("-5.5".to_big_f / "5.5".to_big_f).to_s.should eq("-1") }
it { ("5.5".to_big_f / "-5.5".to_big_f).to_s.should eq("-1") }
expect_raises(DivisionByZero) { 0.1.to_big_f / 0 }
it { ("5.5".to_big_f / 16_u64).to_s.should eq("0.34375") }
it { ("5.5".to_big_f / 16_u8).to_s.should eq("0.34375") }
end

describe "**" do
@@ -65,6 +123,13 @@ describe "BigFloat" do
describe "floor" do
it { 2.1.to_big_f.floor.should eq(2) }
it { 2.9.to_big_f.floor.should eq(2) }
it { -2.9.to_big_f.floor.should eq(-3) }
end

describe "trunc" do
it { 2.1.to_big_f.trunc.should eq(2) }
it { 2.9.to_big_f.trunc.should eq(2) }
it { -2.9.to_big_f.trunc.should eq(-2) }
end

describe "to_f" do
@@ -92,6 +157,7 @@ describe "BigFloat" do
it { "12345678.87654321".to_big_f.to_s.should eq("12345678.87654321") }
it { "9.000000000000987".to_big_f.to_s.should eq("9.000000000000987") }
it { "12345678901234567".to_big_f.to_s.should eq("12345678901234567") }
it { "1234567890123456789".to_big_f.to_s.should eq("1234567890123456789") }
end

describe "#inspect" do
@@ -108,3 +174,9 @@ describe "BigFloat" do
x.clone.should eq(x)
end
end

describe "BigFloat Math" do
it "frexp" do
Math.frexp(0.2.to_big_f).should eq({0.8, -2})
end
end
28 changes: 28 additions & 0 deletions spec/std/big/big_int_spec.cr
Original file line number Diff line number Diff line change
@@ -53,6 +53,29 @@ describe "BigInt" do
[1.1, 1.to_big_i, 3.to_big_i, 2.2].sort.should eq([1, 1.1, 2.2, 3])
end

it "divides and calculs the modulo" do
11.to_big_i.divmod(3.to_big_i).should eq({3, 2})
11.to_big_i.divmod(-3.to_big_i).should eq({-4, -1})

11.to_big_i.divmod(3_i32).should eq({3, 2})
11.to_big_i.divmod(-3_i32).should eq({-4, -1})

10.to_big_i.divmod(2).should eq({5, 0})
11.to_big_i.divmod(2).should eq({5, 1})

10.to_big_i.divmod(2.to_big_i).should eq({5, 0})
11.to_big_i.divmod(2.to_big_i).should eq({5, 1})

10.to_big_i.divmod(-2).should eq({-5, 0})
11.to_big_i.divmod(-2).should eq({-6, -1})

-10.to_big_i.divmod(2).should eq({-5, 0})
-11.to_big_i.divmod(2).should eq({-6, 1})

-10.to_big_i.divmod(-2).should eq({5, 0})
-11.to_big_i.divmod(-2).should eq({5, -1})
end

it "adds" do
(1.to_big_i + 2.to_big_i).should eq(3.to_big_i)
(1.to_big_i + 2).should eq(3.to_big_i)
@@ -222,6 +245,11 @@ describe "BigInt" do
a.to_s(32).should eq(d)
end

it "does to_big_f" do
a = BigInt.new("1234567890123456789")
a.to_big_f.should eq(BigFloat.new("1234567890123456789.0"))
end

describe "#inspect" do
it { "2".to_big_i.inspect.should eq("2_big_i") }
end
14 changes: 14 additions & 0 deletions spec/std/big/big_rational_spec.cr
Original file line number Diff line number Diff line change
@@ -72,10 +72,24 @@ describe BigRational do
r.to_f32.should be_close(f, 0.001)
end

it "#to_big_f" do
r = br(10, 3)
f = 10.to_big_f / 3.to_big_f
r.to_big_f.should be_close(f, 0.001)
end

it "Int#to_big_r" do
3.to_big_r.should eq(br(3, 1))
end

it "Float32#to_big_r" do
0.3333333333333333333333_f32.to_big_r.should eq(br(11184811, 33554432))
end

it "Float64#to_big_r" do
0.3333333333333333333333_f64.to_big_r.should eq(br(6004799503160661, 18014398509481984))
end

it "#<=>(:BigRational) and Comparable" do
a = br(11, 3)
l = br(10, 3)
10 changes: 10 additions & 0 deletions src/big.cr
Original file line number Diff line number Diff line change
@@ -1,3 +1,13 @@
# :nodoc: Forward declarations
struct BigInt < Int
end

struct BigFloat < Float
end

struct BigRational < Number
end

require "./big/lib_gmp"
require "./big/big_int"
require "./big/big_float"
83 changes: 76 additions & 7 deletions src/big/big_float.cr
Original file line number Diff line number Diff line change
@@ -17,6 +17,47 @@ struct BigFloat < Float
LibGMP.mpf_init_set_str(out @mpf, str, 10)
end

def initialize(num : BigInt)
LibGMP.mpf_init(out @mpf)
LibGMP.mpf_set_z(self, num)
end

def initialize(num : BigRational)
LibGMP.mpf_init(out @mpf)
LibGMP.mpf_set_q(self, num)
end

def initialize(num : BigFloat)
LibGMP.mpf_init(out @mpf)
LibGMP.mpf_set(self, num)
end

def initialize(num : Int8 | Int16 | Int32)
LibGMP.mpf_init_set_si(out @mpf, num)
end

def initialize(num : UInt8 | UInt16 | UInt32)
LibGMP.mpf_init_set_ui(out @mpf, num)
end

def initialize(num : Int64)
if LibGMP::Long == Int64
LibGMP.mpf_init_set_si(out @mpf, num)
else
LibGMP.mpf_init(out @mpf)
LibGMP.mpf_set_z(self, num.to_big_i)
end
end

def initialize(num : UInt64)
if LibGMP::ULong == UInt64
LibGMP.mpf_init_set_ui(out @mpf, num)
else
LibGMP.mpf_init(out @mpf)
LibGMP.mpf_set_z(self, num.to_big_i)
end
end

def initialize(num : Number)
LibGMP.mpf_init_set_d(out @mpf, num.to_f64)
end
@@ -51,16 +92,22 @@ struct BigFloat < Float
LibGMP.mpf_cmp(self, other)
end

def <=>(other : Float)
LibGMP.mpf_cmp_d(self, other.to_f64)
def <=>(other : BigInt)
LibGMP.mpf_cmp_z(self, other)
end

def <=>(other : Int::Signed)
LibGMP.mpf_cmp_si(self, other.to_i64)
def <=>(other : Float32 | Float64)
LibGMP.mpf_cmp_d(self, other.to_f64)
end

def <=>(other : Int::Unsigned)
LibGMP.mpf_cmp_ui(self, other.to_u64)
def <=>(other : Number)
if other.is_a?(Int8 | Int16 | Int32) || (LibGMP::Long == Int64 && other.is_a?(Int64))
LibGMP.mpf_cmp_si(self, other)
elsif other.is_a?(UInt8 | UInt16 | UInt32) || (LibGMP::ULong == UInt64 && other.is_a?(UInt64))
LibGMP.mpf_cmp_ui(self, other)
else
LibGMP.mpf_cmp(self, other.to_big_f)
end
end

def -
@@ -81,7 +128,11 @@ struct BigFloat < Float

def /(other : Number)
raise DivisionByZero.new if other == 0
BigFloat.new { |mpf| LibGMP.mpf_div(mpf, self, other.to_big_f) }
if other.is_a?(UInt8 | UInt16 | UInt32) || (LibGMP::ULong == UInt64 && other.is_a?(UInt64))
BigFloat.new { |mpf| LibGMP.mpf_div_ui(mpf, self, other) }
else
BigFloat.new { |mpf| LibGMP.mpf_div(mpf, self, other.to_big_f) }
end
end

def **(other : Int)
@@ -100,6 +151,10 @@ struct BigFloat < Float
BigFloat.new { |mpf| LibGMP.mpf_floor(mpf, self) }
end

def trunc
BigFloat.new { |mpf| LibGMP.mpf_trunc(mpf, self) }
end

def to_f64
LibGMP.mpf_get_d(self)
end
@@ -222,3 +277,17 @@ class String
BigFloat.new(self)
end
end

module Math
def frexp(value : BigFloat)
LibGMP.mpf_get_d_2exp(out exp, value) # we need BigFloat frac, so will skip Float64 one.
frac = BigFloat.new do |mpf|
if exp >= 0
LibGMP.mpf_div_2exp(mpf, value, exp)
else
LibGMP.mpf_mul_2exp(mpf, value, -exp)
end
end
{frac, exp}
end
end
81 changes: 73 additions & 8 deletions src/big/big_int.cr
Original file line number Diff line number Diff line change
@@ -195,6 +195,35 @@ struct BigInt < Int
unsafe_truncated_mod(other)
end

def divmod(number : BigInt)
check_division_by_zero number

unsafe_floored_divmod(number)
end

def divmod(number : LibGMP::ULong)
check_division_by_zero number
unsafe_floored_divmod(number)
end

def divmod(number : Int::Signed)
check_division_by_zero number
if number > 0 && number <= LibC::Long::MAX
unsafe_floored_divmod(LibGMP::ULong.new(number))
else
divmod(number.to_big_i)
end
end

def divmod(number : Int::Unsigned)
check_division_by_zero number
if number <= LibC::ULong::MAX
unsafe_floored_divmod(LibGMP::ULong.new(number))
else
divmod(number.to_big_i)
end
end

def unsafe_floored_mod(other : BigInt) : BigInt
BigInt.new { |mpz| LibGMP.fdiv_r(mpz, self, other) }
end
@@ -211,6 +240,30 @@ struct BigInt < Int
BigInt.new { |mpz| LibGMP.tdiv_r_ui(mpz, self, other.abs) }
end

def unsafe_floored_divmod(number : BigInt)
the_q = BigInt.new
the_r = BigInt.new { |r| LibGMP.fdiv_qr(the_q, r, self, number) }
{the_q, the_r}
end

def unsafe_floored_divmod(number : LibGMP::ULong)
the_q = BigInt.new
the_r = BigInt.new { |r| LibGMP.fdiv_qr_ui(the_q, r, self, number) }
{the_q, the_r}
end

def unsafe_truncated_divmod(number : BigInt)
the_q = BigInt.new
the_r = BigInt.new { |r| LibGMP.tdiv_qr(the_q, r, self, number) }
{the_q, the_r}
end

def unsafe_truncated_divmod(number : LibGMP::ULong)
the_q = BigInt.new
the_r = BigInt.new { |r| LibGMP.tdiv_qr_ui(the_q, r, self, number) }
{the_q, the_r}
end

def ~ : BigInt
BigInt.new { |mpz| LibGMP.com(mpz, self) }
end
@@ -311,39 +364,47 @@ struct BigInt < Int
end

def to_i8
to_i64.to_i8
to_i32.to_i8
end

def to_i16
to_i64.to_i16
to_i32.to_i16
end

def to_i32
to_i64.to_i32
LibGMP.get_si(self).to_i32
end

def to_i64
LibGMP.get_si(self)
if LibGMP::Long == Int64 || (self <= Int32::MAX && self >= Int32::MIN)
LibGMP.get_si(self).to_i64
else
to_s.to_i64
end
end

def to_u
to_u32
end

def to_u8
to_u64.to_u8
to_u32.to_u8
end

def to_u16
to_u64.to_u16
to_u32.to_u16
end

def to_u32
to_u64.to_u32
LibGMP.get_ui(self).to_u32
end

def to_u64
LibGMP.get_ui(self).to_u64
if LibGMP::ULong == UInt64 || (self <= UInt32::MAX && self >= UInt32::MIN)
LibGMP.get_ui(self).to_u64
else
to_s.to_u64
end
end

def to_f
@@ -362,6 +423,10 @@ struct BigInt < Int
self
end

def to_big_f
BigFloat.new { |mpf| LibGMP.mpf_set_z(mpf, mpz) }
end

def clone
self
end
35 changes: 33 additions & 2 deletions src/big/big_rational.cr
Original file line number Diff line number Diff line change
@@ -8,7 +8,7 @@ require "big"
# ```
# require "big_rational"
#
# r = BigRational.new(BigInt.new(7), BigInt.new(3))
# r = BigRational.new(7.to_big_i, 3.to_big_i)
# r.to_s # => "7/3"
#
# r = BigRational.new(3, -9)
@@ -21,6 +21,9 @@ struct BigRational < Number
include Comparable(Int)
include Comparable(Float)

private MANTISSA_BITS = 53
private MANTISSA_SHIFT = (1_i64 << MANTISSA_BITS).to_f64

# Create a new `BigRational`.
#
# If *denominator* is 0, this will raise an exception.
@@ -41,6 +44,21 @@ struct BigRational < Number
initialize(num, 1)
end

# Creates a exact representation of float as rational.
def initialize(num : Float)
# It ensures that `BigRational.new(f) == f`
# It relies on fact, that mantissa is at most 53 bits
frac, exp = Math.frexp num
ifrac = (frac.to_f64 * MANTISSA_SHIFT).to_i64
exp -= MANTISSA_BITS
initialize ifrac, 1
if exp >= 0
LibGMP.mpq_mul_2exp(out @mpq, self, exp)
else
LibGMP.mpq_div_2exp(out @mpq, self, -exp)
end
end

# :nodoc:
def initialize(@mpq : LibGMP::MPQ)
end
@@ -64,8 +82,12 @@ struct BigRational < Number
LibGMP.mpq_cmp(mpq, other)
end

def <=>(other : Float32 | Float64)
self <=> BigRational.new(other)
end

def <=>(other : Float)
self.to_f <=> other
to_big_f <=> other.to_big_f
end

def <=>(other : Int)
@@ -156,6 +178,10 @@ struct BigRational < Number
LibGMP.mpq_get_d(mpq)
end

def to_big_f
BigFloat.new { |mpf| LibGMP.mpf_set_q(mpf, mpq) }
end

# Returns the string representing this rational.
#
# Optionally takes a radix base (2 through 36).
@@ -237,6 +263,11 @@ end
struct Float
include Comparable(BigRational)

# Returns a `BigRational` representing this float.
def to_big_r
BigRational.new(self)
end

def <=>(other : BigRational)
-(other <=> self)
end
28 changes: 25 additions & 3 deletions src/big/lib_gmp.cr
Original file line number Diff line number Diff line change
@@ -61,8 +61,15 @@ lib LibGMP
fun fdiv_r = __gmpz_fdiv_r(rop : MPZ*, op1 : MPZ*, op2 : MPZ*)
fun fdiv_r_ui = __gmpz_fdiv_r_ui(rop : MPZ*, op1 : MPZ*, op2 : ULong)

fun fdiv_qr = __gmpz_fdiv_qr(q : MPZ*, r : MPZ*, n : MPZ*, d : MPZ*)
fun fdiv_qr_ui = __gmpz_fdiv_qr_ui(q : MPZ*, r : MPZ*, n : MPZ*, d : ULong) : ULong

fun tdiv_r = __gmpz_tdiv_r(rop : MPZ*, op1 : MPZ*, op2 : MPZ*)
fun tdiv_r_ui = __gmpz_tdiv_r_ui(rop : MPZ*, op1 : MPZ*, op2 : ULong)
fun tdiv_ui = __gmpz_tdiv_ui(op1 : MPZ*, op2 : ULong) : ULong

fun tdiv_qr = __gmpz_tdiv_qr(q : MPZ*, r : MPZ*, n : MPZ*, d : MPZ*)
fun tdiv_qr_ui = __gmpz_tdiv_qr_ui(q : MPZ*, r : MPZ*, n : MPZ*, d : ULong) : ULong

fun neg = __gmpz_neg(rop : MPZ*, op : MPZ*)
fun abs = __gmpz_abs(rop : MPZ*, op : MPZ*)
@@ -90,6 +97,9 @@ lib LibGMP
fun cmp_ui = __gmpz_cmp_ui(op1 : MPZ*, op2 : ULong) : Int
fun cmp_d = __gmpz_cmp_d(op1 : MPZ*, op2 : Double) : Int

# # Conversion
fun get_d_2exp = __gmpz_get_d_2exp(exp : Long*, op : MPZ*) : Double

# # Number Theoretic Functions

fun gcd = __gmpz_gcd(rop : MPZ*, op1 : MPZ*, op2 : MPZ*)
@@ -143,35 +153,47 @@ lib LibGMP
fun mpf_init2 = __gmpf_init2(x : MPF*, prec : BitcntT)
fun mpf_init_set_d = __gmpf_init_set_d(rop : MPF*, op : Double)
fun mpf_init_set_str = __gmpf_init_set_str(rop : MPF*, str : UInt8*, base : Int) : Int
fun mpf_init_set_ui = __gmpf_init_set_ui(rop : MPF*, op : ULong)
fun mpf_init_set_si = __gmpf_init_set_si(rop : MPF*, op : Long)

# # Precision
fun mpf_set_default_prec = __gmpf_set_default_prec(prec : BitcntT)
fun mpf_get_default_prec = __gmpf_get_default_prec : BitcntT

# # I/O
# # Conversion
fun mpf_get_str = __gmpf_get_str(str : UInt8*, expptr : MpExp*, base : Int, n_digits : LibC::SizeT, op : MPF*) : UInt8*
fun mpf_get_d = __gmpf_get_d(op : MPF*) : Double
fun mpf_set_d = __gmpf_set_d(op : MPF*, op : Double)
fun mpf_set = __gmpf_set(op : MPF*, op : MPF*)
fun mpf_set_z = __gmpf_set_z(rop : MPF*, op : MPZ*)
fun mpf_set_q = __gmpf_set_q(rop : MPF*, op : MPQ*)
fun mpf_get_si = __gmpf_get_si(op : MPF*) : Long
fun mpf_get_ui = __gmpf_get_ui(op : MPF*) : ULong
fun mpf_ceil = __gmpf_ceil(rop : MPF*, op : MPF*)
fun mpf_floor = __gmpf_floor(rop : MPF*, op : MPF*)
fun mpf_get_d_2exp = __gmpf_get_d_2exp(exp : Long*, op : MPF*) : Double

# # Arithmetic
fun mpf_add = __gmpf_add(rop : MPF*, op1 : MPF*, op2 : MPF*)
fun mpf_sub = __gmpf_sub(rop : MPF*, op1 : MPF*, op2 : MPF*)
fun mpf_mul = __gmpf_mul(rop : MPF*, op1 : MPF*, op2 : MPF*)
fun mpf_div = __gmpf_div(rop : MPF*, op1 : MPF*, op2 : MPF*)
fun mpf_div_ui = __gmpf_div_ui(rop : MPF*, op1 : MPF*, op2 : ULong)
fun mpf_neg = __gmpf_neg(rop : MPF*, op : MPF*)
fun mpf_abs = __gmpf_abs(rop : MPF*, op : MPF*)
fun mpf_pow_ui = __gmpf_pow_ui(rop : MPF*, op1 : MPF*, op2 : ULong)
fun mpf_mul_2exp = __gmpf_mul_2exp(rop : MPF*, op1 : MPF*, op2 : BitcntT)
fun mpf_div_2exp = __gmpf_div_2exp(rop : MPF*, op1 : MPF*, op2 : BitcntT)

# # Comparison
fun mpf_cmp = __gmpf_cmp(op1 : MPF*, op2 : MPF*) : Int
fun mpf_cmp_d = __gmpf_cmp_d(op1 : MPF*, op2 : Double) : Int
fun mpf_cmp_ui = __gmpf_cmp_ui(op1 : MPF*, op2 : ULong) : Int
fun mpf_cmp_si = __gmpf_cmp_si(op1 : MPF*, op2 : Long) : Int
fun mpf_cmp_z = __gmpf_cmp_z(op1 : MPF*, op2 : MPZ*) : Int

# # Miscellaneous
fun mpf_ceil = __gmpf_ceil(rop : MPF*, op : MPF*)
fun mpf_floor = __gmpf_floor(rop : MPF*, op : MPF*)
fun mpf_trunc = __gmpf_trunc(rop : MPF*, op : MPF*)
fun mpf_integer_p = __gmpf_integer_p(op : MPF*) : Int

# # Memory

0 comments on commit d1960a5

Please sign in to comment.