Skip to content
New issue

Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.

By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.

Already on GitHub? Sign in to your account

Implement BigDecimal #4876

Merged
merged 24 commits into from Nov 7, 2017
Merged

Implement BigDecimal #4876

merged 24 commits into from Nov 7, 2017

Conversation

vegai
Copy link
Contributor

@vegai vegai commented Aug 23, 2017

This PR adds a BigDecimal implementation.

The motivation for having BigDecimals is to have an arbitrary precision exact decimal type. This is required at least in financial calculations, where the precision of Floats and is not enough and BigRationals may have other problems due to denominator potentially being something else than 10**x. At least Ruby, Python and Java contain something like this in their standard libs.

The design is mostly adapted from bigdecimal-rs written for Rust. It holds its actual value in a BigInt, and a scale (decimal point place) in UInt64. It currently contains basic + - * / arithmetics. Possible future needs: implementation of ** (power) and supporting scientific "123E45" notation.

Please critique liberally. This would be my first larger Crystal contribution.

# Set maximum iterations used in division operation. This implicitly
# defines the maximum precision of divisions in cases where the
# division is not exact.
def self.set_max_div_iterations(x : Int)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please use descriptive names for arguments.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

=> new_max_div

# Create a new `BigDecimal` from a String.
#
# Allows only valid number strings with an optional negative sign.
def initialize(s : String)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Use ditto to use the same comment as in the previous declaration.

https://crystal-lang.org/docs/conventions/documenting_code.html

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

=> str

@makenowjust I guess this comment didn't apply here?

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@makenowjust Quoted remark applies to documentation, not code-review comments, mind you.

end

# from Int
def initialize(i : Int)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

=> num

end

# from Float is not supported due to precision loss risks. This call fails at compile time.
def initialize(f : Float)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

=> num

end

private def power_ten_to(x : Int) : Int
BigInt.new(10) ** x
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

TEN ** x

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

=> TEN

@vegai vegai force-pushed the bigdecimal branch 3 times, most recently from def36c3 to 6e9a815 Compare August 24, 2017 05:36
end

struct Float
# from Float is not supported due to precision loss risks. This call fails at compile time.
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

I'd use full sentence here, like: "Casting from Float is not supported due to ..."

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

So changed.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@vegai you should use ` around Float in your comment: Casting from `Float` ...

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Marked this Float and all the other similar ones too.

include Comparable(BigDecimal)

# Convert `Int` to `BigDecimal`
def to_big_d
Copy link
Contributor

@akzhan akzhan Aug 25, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Looks like you forget to declare

struct BigDecimal
  def to_big_d
    self
  end
end

to optimize BigDecimal case of to_big_d (we need no copy here).

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yes. Added.

elsif @scale > s.size
io << "0."
(@scale - s.size).times do
io << "0"
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You could use a Char here.

Copy link
Contributor

@akzhan akzhan Aug 25, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, string is better here because need no conversion from Char to utf8 bytes.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@Sija I'm wrong! Unbelievable!

➜  crystal git:(bigfloat-frexp) ✗ bin/crystal 1.cr --no-debug --release
Using compiled compiler at `.build/crystal'
            char 370.13  (   2.7ms) (± 0.91%)       fastest
          string 150.32  (  6.65ms) (± 1.97%)  2.46× slower
  byte from char  12.61  ( 79.32ms) (± 2.65%) 29.36× slower
byte from string 133.63  (  7.48ms) (± 1.40%)  2.77× slower
            byte 132.72  (  7.53ms) (± 1.82%)  2.79× slower
require "benchmark"

Benchmark.ips do |x|
  x.report("char") { io = IO::Memory.new; 1_000_000.times { io << '.' } }
  x.report("string") { io = IO::Memory.new; 1_000_000.times { io << "." } }
  x.report("byte from char") { io = IO::Memory.new; 1_000_000.times { io << '.'.bytes } }
  x.report("byte from string") { io = IO::Memory.new; 1_000_000.times { io << ".".byte_at(0) } }
  x.report("byte") { b = ".".byte_at(0); io = IO::Memory.new; 1_000_000.times { io << b } }
end

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

@vegai Could you please include above tweaks?

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Huh, interesting :) Seems almost like a performance bug somewhere.

But will change these to chars then.

io << s
else
offset = s.size - @scale
io << s[0...offset] << "." << s[offset..-1]
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

ditto

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Done

@akzhan
Copy link
Contributor

akzhan commented Aug 26, 2017

LGTM


(BigDecimal.new(1) > BigDecimal.new(1)).should be_false
(BigDecimal.new("1.00000000000000000000000000000000000001") > BigDecimal.new(1)).should be_true
(BigDecimal.new("0.99999999999999999999999999999999999999") > BigDecimal.new(1)).should be_false
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

You should test less than here.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Added < tests

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

(BigDecimal.new("0.99999999999999999999999999999999999999") < BigDecimal.new(1)).should be_true

(BigDecimal.new("-1") < BigDecimal.new("1")).should be_true
end

it "arithmetic that beats float precision" do
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

it "keeps precision"? In general these it names don't flow well.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah, I wasn't thinking at all there. Changed all the descriptions.


include Comparable(BigDecimal)
include Comparable(Int)
include Comparable(String)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

We shouldn't be comparable with string (at least I don't think any other numeric is) but we should be comparable with all other numbers not just int. We shouldn't need multiple comparable includes here, just Comparable(Numeric).

Copy link
Contributor Author

@vegai vegai Aug 27, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Replaced Int and String with Comparable(Number)

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oops, misremembered the name. Thanks!

struct BigDecimal
ZERO = BigInt.new(0)
TEN = BigInt.new(10)
@@max_div_iterations = 100_u64
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please use class_property. I'm not entirely sure I like that this is global, maybe we should make it configurable per div call with the default being this property.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah, I thought it was a bit awkward too. The original algorithm in Rust just had this value hardcoded inside the div method. I'll take a look at configuring it per div call. I cannot make this an optional parameter of / though, can I?

Copy link
Contributor Author

@vegai vegai Aug 28, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Made it configurable per div call as suggested: added a div function with the optional parameter, and made / call that one. DEFAULT_MAX_DIV_ITERATIONS is now a class constant.


private property value : BigInt
private property scale : UInt64
getter value, scale
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please don't do this. Use a public getter and simply use @value when you want to set.

For that matter, you should never need to set these values because this struct should be immutable.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Hmm, I didn't quite get the gist here. Doesn't this combo make the value immutable from the outside world? Or does Crystal have better immutability protections that I've missed?

check_division_by_zero other

scale = @scale - other.scale
n, d = @value, other.@value
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Please don't use single character variable names.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

scale = @scale - other.scale
n, d = @value, other.@value

quotient, remainder = n.tdiv(d), n.remainder(d)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Could you use divmod here?

Copy link
Contributor Author

@vegai vegai Aug 27, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

They're not quite the same. divmod floors negative integers down, which doesn't work here without additional changes.

1.divmod(-2) => {-1, -1}
1.tdiv(-2) => 0
1.remainder(-2) => 1

But I'll think a bit if it would be a good idea to adapt the algo to divmod.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Huh, unearthed a bug here. -1 / -2 gives us -0.5 currently.

Copy link
Contributor Author

@vegai vegai Aug 28, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed bugs, added bunch of div tests, and moved to divmod.

end

# from `Int`
def initialize(num : Int)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

There should be a far faster way to initialize from integers than via to_s.

Copy link
Contributor Author

@vegai vegai Aug 28, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh, whoops. Somebody was lazy :P Fixed.

remainder = remainder * TEN

i = 0
while remainder != ZERO && i < @@max_div_iterations
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Shouldn't you raise if you reach max_div_iterations, not give the wrong result.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

It's not very exceptional, since simple calculations like 1/3 hit this.

Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Oh never mind then. I didn't read the code properly.

struct Float
# Casting from `Float` is not supported due to precision loss risks. This call fails at compile time.
def to_big_d
{% raise "Initializing from Float is risky due to loss of precision -- convert rather from Int or String" %}
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Ditto

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Same as before, I guess?

@vegai vegai force-pushed the bigdecimal branch 2 times, most recently from b8b2025 to 8a73f37 Compare August 27, 2017 13:13
end

it "keeps precision" do
oneThousandth = BigDecimal.new("0.001")
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

please, use snake_case for variable names; we ain't in JavaScript Land Dorothy ;)

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Heh. Fixed.

@vegai vegai force-pushed the bigdecimal branch 2 times, most recently from e1c41d9 to d3728f0 Compare August 28, 2017 12:03
return BigDecimal.new(quotient, scale) if remainder == ZERO
# quotient, remainder = n.tdiv(d), n.remainder(d)
quotient, remainder = n.divmod(d)
puts "n #{n} d #{d} q #{quotient} r #{remainder}"
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Debug leftovers.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Yeah, intermediate commits to save work. Removed afterwards

struct BigDecimal
ZERO = BigInt.new(0)
TEN = BigInt.new(10)
DEFAULT_MAX_DIV_ITERATIONS = 100_u64
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Personally I wouldn't bother making this a constant but it's not worth any effort making it not a constant.

So ignore this comment.

@vegai vegai force-pushed the bigdecimal branch 3 times, most recently from 5470f7b to 9346020 Compare August 28, 2017 21:44
@akzhan
Copy link
Contributor

akzhan commented Sep 6, 2017

Looks like You forgot about

struct BigDecimal
  # Returns *num*. Useful for generic code that does `T.new(...)` with `T`
  # being a `Number`.
  def self.new(num : BigDecimal)
    num
  end

Some info here: #2292.

@vegai vegai force-pushed the bigdecimal branch 2 times, most recently from e050e69 to 1b202bb Compare September 7, 2017 10:57
@vegai
Copy link
Contributor Author

vegai commented Sep 7, 2017

@akzhan Thanks, added that.

@vegai
Copy link
Contributor Author

vegai commented Oct 16, 2017

Added to_f/u/i implementations and a few specs. to_f goes via to_s while to_u and _i scale and truncate like Java's implementation.

Also rebased against master and changed require "big_int" to require "big".

(@value / TEN ** @scale)
else
-(@value.abs / TEN ** @scale)
end.to_i
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

No, we never chain a method call after end. The correct way to write this is to stick the to_i on the end of the if branches, which works because of explicit return.

If this wasn't the final (only) statement in the method, we simply assign to a variable inside if:

if @value >= 0
  int_value = (@value / TEN ** @scale).to_i
else
  int_value = -(@value.abs / TEN ** @scale).to_i
end

# use int_value

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Righto. Fixed.

@vegai
Copy link
Contributor Author

vegai commented Nov 6, 2017

Should this PR be in the "Numbers" project?

# defines a maximum number of iterations in case the division is not exact.
#
# ```
# BigDecimal(1).div(BigDecimal(2)) => BigDecimal(@value=5, @scale=2)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Missing # before =>. On the line below as well.

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Roger, fixed.

div other
end

# Divides self with another `BigDecimal`, with a optionally configurable max_div_iterations, which
Copy link
Contributor

@Sija Sija Nov 6, 2017

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

max_div_iterations -> *max_div_iterations*

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed.

hasher.string(self.to_s)
end

# Returns the quotient as absolutely negative if self and other have different signs,
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

quotient -> *quotient*

Copy link
Contributor Author

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Fixed (also line below).

Thanks!

@mverzilli mverzilli merged commit 1ccd22b into crystal-lang:master Nov 7, 2017
@mverzilli mverzilli added this to the Next milestone Nov 7, 2017
@onemanstartup
Copy link

Thank you! 🎉

@mverzilli
Copy link

Thank you @vegai! Amazing work, and outstanding patience to bear with reviews :)

end

def hash(hasher)
hasher.string(self.to_s)
Copy link
Contributor

Choose a reason for hiding this comment

The reason will be displayed to describe this comment to others. Learn more.

Of course it must be rewritten using number normalization.

But it will be anyway later.

@Sija
Copy link
Contributor

Sija commented Nov 7, 2017

This PR added src/big_decimal.cr which got obsolete because of #5121.

@Sija
Copy link
Contributor

Sija commented Nov 7, 2017

btw, why BigDecimal doesn't inherit from Number?

@akzhan
Copy link
Contributor

akzhan commented Nov 12, 2017

@oprypin Done - #5276

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Projects
None yet
Development

Successfully merging this pull request may close these issues.

None yet