juliamath / fixedpointdecimals.jl Goto Github PK

Had once forgotten to add the second type parameter but I was met with a stack overflow:

julia> FixedDecimal{Int8}(5)
ERROR: StackOverflowError:
Stacktrace:
     [1] convert(#unused#::Type{FixedDecimal{Int8}}, x::Int64)
       @ Base ./number.jl:7
     [2] (FixedDecimal{Int8})(x::Int64)
       @ FixedPointDecimals ~/.julia/packages/FixedPointDecimals/GFltp/src/FixedPointDecimals.jl:103
--- the last 2 lines are repeated 39990 more times ---
 [79983] convert(#unused#::Type{FixedDecimal{Int8}}, x::Int64)
       @ Base ./number.jl:7

We already support converting a FixedDecimal to a Rational, via:

We should also provide numerator() and denominator(), as part of that interface. They might be implemented like this:

function Base.numerator(x::FixedDecimal{T,f})::T where {T, f}
    return value(x)
end
function Base.denominator(x::FixedDecimal{T,f})::T where {T, f}
    return coefficient(x)
end

Splitting out the benchmark discussion from #36.

Here's the benchmark in a gist:
https://gist.github.com/NHDaly/a8fae0d1d65ab1066c585c27e54146fa

And the results in a google spreadsheet:
https://docs.google.com/spreadsheets/d/1Lc3ughgwwK25cpwbnuLRxw19EtaMxdCsMmtnspT_4H8/edit?usp=sharing

Here are the results:

Here are my current question:

• For some reason, even just element-wise copying an array of FixedDecimal{Int128, 2} into another array, allocates like crazy. (14,000,000 allocations / 1,000,000 elements).
  • Where do these allocations come from?
• / and * of FixedDecimal{Int64, 2} are more expensive than for FixedDecimal{Int32, 2}., by a factor of around 1.5x each, whereas / and * for Int64 and Int32 are almost identical.
  • My current guess is that this might be related to promoting to Int128 during those operations (due to widemul), which seems to be slower than Int64 across the board.
• / for Int128 is like 6x slower than for Int32! Where does that come from?

julia> one = FixedDecimal{Int,2}(1)
FixedDecimal{Int64,2}(1.00)

julia> one/3
FixedDecimal{Int64,2}(0.33)

julia> one/3.0
0.3333333333333333

Intuitively, I would expect one/3 === one/3.0 since

julia> 1/3 === 1/3.0
true

Strictly speaking, one/3 should probably also be a Float64, BUT...

I think users of this package might reasonably expect both

julia> one/3
FixedDecimal{Int64,2}(0.33)

and

julia> one/3.0
FixedDecimal{Int64,2}(0.33)

Otherwise, there would need to be a lot of conversion in the code that would kind of defeat its purpose. For example, if you wanted the result of one/3.0 to remain a FixedDecimal, you'd need to do something like

> onethird = FixedDecimal{Int,2}(one/3.0)

I think we should either:

1. Make one/3 also a Float64 so one/3 === one/3.0 or
2. Make one/3.0 also a FixedDecimal so one/3 === one/3.0

I kind of prefer the latter, but in any case it currently seems inconsistent.

What do you think?

So there's this problem, well described by @omus here:
#30

TLDR, constructing these is way slower than it needs to be. It should be the same speed as regular ints, but it isn't:

julia> function _test(max)
         FD_t = FixedPointDecimals.FixedDecimal{Int64, 0}
         sum(1:10)
         sum(FD_t(1):FD_t(10))
         @time X = collect(1:max)
         @time sum(X)
         @time Y = collect(FD_t(1) : FD_t(max))
         @time sum(Y)
         nothing
       end
>> _test (generic function with 1 method)

julia> _test(1)  # warmup
...

julia> _test(10_000_000)
  0.114792 seconds (2 allocations: 76.294 MiB, 60.54% gc time)
  0.006643 seconds
  4.474370 seconds (2 allocations: 76.294 MiB, 0.31% gc time)
  0.504544 seconds

I opened and closed a bunch of PRs here so I could discuss other alternatives we might consider, but I currently think this one is best:
#34

On Julia 1.6-dev (57e6bead349117417c3b0b0ad4fe1b248197fee5, tip on 10/20), on up Pkg complains

ERROR: project file for FixedPointDecimals is missing a `version` entry

Best! :)

Consider:

julia> @which FD{BigInt,2}(2) + 2
+(x::Number, y::Number)
     @ Base promotion.jl:410

julia> @code_typed FD{BigInt,2}(2) + 2
CodeInfo(
1 ─ %1 = invoke Base.GMP.MPZ.set_si(10::Int64)::BigInt
│   %2 = invoke Base.GMP.bigint_pow(%1::BigInt, 2::Int64)::BigInt
│   %3 = invoke Base.GMP.MPZ.mul_si(%2::BigInt, y::Int64)::BigInt
│   %4 = Base.getfield(x, :i)::BigInt
│   %5 = invoke Base.GMP.MPZ.add(%4::BigInt, %3::BigInt)::BigInt
│   %6 = %new(FixedDecimal{BigInt, 2}, %5)::FixedDecimal{BigInt, 2}
└──      return %6
) => FixedDecimal{BigInt, 2}

julia> @code_typed optimize=false FD{BigInt,2}(2) + 2
CodeInfo(
1 ─ %1 = Base.:+::Core.Const(+)
│   %2 = Base.promote(x, y)::Tuple{FixedDecimal{BigInt, 2}, FixedDecimal{BigInt, 2}}
│   %3 = Core._apply_iterate(Base.iterate, %1, %2)::FixedDecimal{BigInt, 2}
└──      return %3
) => FixedDecimal{BigInt, 2}

If we instead had special-cased operators for ::FD{BigInt}, ::Integer we could avoid the promotion and save an allocation.

@TotalVerb the changes you did in 7623549 seemed to have undone some of the changes in d7c2d5c.

import FixedPointDecimals: FD
for i in 0:18
    println(lpad(i, 2), " ", repr(trunc(FD{Int,i}, 2.3)))
end

On revision d7c2d5c we get:

 0 FixedDecimal{Int64,0}(2)
 1 FixedDecimal{Int64,1}(2.2)
 2 FixedDecimal{Int64,2}(2.29)
 3 FixedDecimal{Int64,3}(2.299)
 4 FixedDecimal{Int64,4}(2.2999)
 5 FixedDecimal{Int64,5}(2.29999)
 6 FixedDecimal{Int64,6}(2.299999)
 7 FixedDecimal{Int64,7}(2.2999999)
 8 FixedDecimal{Int64,8}(2.29999999)
 9 FixedDecimal{Int64,9}(2.299999999)
10 FixedDecimal{Int64,10}(2.2999999999)
11 FixedDecimal{Int64,11}(2.29999999999)
12 FixedDecimal{Int64,12}(2.299999999999)
13 FixedDecimal{Int64,13}(2.2999999999999)
14 FixedDecimal{Int64,14}(2.29999999999999)
15 FixedDecimal{Int64,15}(2.299999999999999)
16 FixedDecimal{Int64,16}(2.2999999999999998)
17 FixedDecimal{Int64,17}(2.29999999999999984)
18 FixedDecimal{Int64,18}(2.299999999999999808)

While on revision 7623549:

 0 FixedDecimal{Int64,0}(2)
 1 FixedDecimal{Int64,1}(2.2)
 2 FixedDecimal{Int64,2}(2.29)
 3 FixedDecimal{Int64,3}(2.299)
 4 FixedDecimal{Int64,4}(2.2999)
 5 FixedDecimal{Int64,5}(2.29999)
 6 FixedDecimal{Int64,6}(2.299999)
 7 FixedDecimal{Int64,7}(2.2999999)
 8 FixedDecimal{Int64,8}(2.29999999)
 9 FixedDecimal{Int64,9}(2.299999999)
10 FixedDecimal{Int64,10}(2.2999999999)
11 FixedDecimal{Int64,11}(2.29999999999)
12 FixedDecimal{Int64,12}(2.299999999999)
13 FixedDecimal{Int64,13}(2.2999999999999)
14 FixedDecimal{Int64,14}(2.29999999999999)
15 FixedDecimal{Int64,15}(2.299999999999999)
16 FixedDecimal{Int64,16}(2.3000000000000000)  # The issue
17 FixedDecimal{Int64,17}(2.29999999999999968)
18 FixedDecimal{Int64,18}(2.299999999999999744)

I'm think there's a bug in the implementation of _round_to_even. Unfortunately, i'm not exactly sure what the logic in that function is supposed to be doing, so I don't know how to fix it.

Here are the inputs I came across that expose the bug. I didn't come up with them myself, I just found them from some data, so I'm sure this isn't the simplest illustration of whatever the bug is:

julia> begin
         dividend = UInt128(0x5fffffffffffffffffffffffffffffeb)
         divisor  = UInt128(0x40000000000000000000000000000000)
         @show dividend/divisor
         quotient, remainder = fldmod(dividend, divisor)
         @show quotient,remainder
         @show quotient + remainder/divisor
         out = FixedPointDecimals._round_to_even(quotient, remainder, divisor)
         @test out == 0x2
       end
dividend / divisor = 1.5
(quotient, remainder) = (0x00000000000000000000000000000001, 0x1fffffffffffffffffffffffffffffeb)
quotient + remainder / divisor = 1.5
Test Failed at none:9
  Expression: out == 0x02
   Evaluated: 0x00000000000000000000000000000001 == 0x02
ERROR: There was an error during testing

Dividing these two numbers returns the decimal value 1.5. This should round to 2, according to the "round to even" rules, but that function instead returns 1.

I'm pretty sure all the preconditions are met:

(EDIT: Oops, fixed the numbers to correctly show the problem.)

Example:

julia> parse(Int64, "    5   ")
5

julia> parse(FixedDecimal{Int64,2}, "    5.0   ")
ERROR: ArgumentError: invalid digit: ' '

julia> parse(FixedDecimal{Int64,2}, "5.0")
FixedDecimal{Int64,2}(5.00)

julia> parse(Float64, "    3.14   ")
3.14

julia> parse(Float64, "    3 . 14   ")
ERROR: ArgumentError: cannot parse "    3 . 14   " as Float64

I'm not sure how easy this would be, but if it's at all possible, I'd be very interested in an extension of this that allows for arbitrary bases--this would have been very useful when working with digital nets, which involve a lot of operations on small numbers in prime bases.

Operations like * or \ can be lossy because they can cause the number of fractional digits to exceed the precision of the FD type, e.g.:

julia> FixedDecimal{Int,2}(1.11) * FixedDecimal{Int,2}(1.11)
FixedDecimal{Int64,2}(1.23)

while the precise answer would be FixedDecimal{Int64,4}(1.2321). During this computation, we materialize the result in full precision and then use _round_to_nearest to round to fix the FD type. It would be good to have the option to make such lossy operations throw an error by making the _round_to_nearest use RoundThrows rounding mode so that the user can be sure that their e.g. financial reports are exact. We already support RoundThrows for parsing.

This could be a global toggle in the style of ToggleableAsserts.jl .

It looks like there were two tests that were covered by Currencies but not by the FixedDecimal tests of Currencies, and are now uncovered.

v0.2.1 was tagged on github, but not METADATA.

Code to test, using Julia 1.6.6 and FixedPointDecimals 0.4.0:

julia> using FixedPointDecimals

julia> tryparse(FixedDecimal{Int64,2},"1.5")
ERROR: MethodError: no method matching tryparse(::Type{FixedDecimal{Int64, 2}}, ::String)
Closest candidates are:
  tryparse(::Type{Complex{S}}, ::AbstractString) where S<:Real at parse.jl:384
  tryparse(::Type{T}, ::AbstractString) where T<:Dates.TimeType at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.6/Dates/src/parse.jl:288
  tryparse(::Type{T}, ::AbstractString, ::Dates.DateFormat) where T<:Dates.TimeType at /Users/julia/buildbot/worker/package_macos64/build/usr/share/julia/stdlib/v1.6/Dates/src/parse.jl:288
  ...
Stacktrace:
 [1] top-level scope
   @ REPL[2]:1

julia>

It might be useful to look at the base implementation of parse to fix this

I can't help but notice that convert(FD, 0.333) is valid, whereas convert(FD, 1//3) isn't (throws InexactError). The difference comes down how adding round in convert(FD, ::Rational).

Is there a good reason the behaviour of Rational and Float are not consistent?

TagBot complained here: #65

Looks like this tag still does not exist, so there is likely a problem with TagBot configuration. In the meantime, this tag should be created manually.

For example

julia> using FixedPointDecimals

julia> @time convert(FixedDecimal{Int,2}, Int128(1))
  0.000005 seconds (7 allocations: 128 bytes)
FixedDecimal{Int64,2}(1.00)

allocates a BigInt because a widemul is used to carry out the multiplication between the coefficient and the Int128 value during the conversion.
This is problematic performance-wise.

One workaround would be to convert the coefficient to an Int128 and then use Base.mul_with_overflow, throwing an InexactError manually on overflow.

Newer versions of Julia come with Base.checked_pow(::Integer, ::Integer), which needs to be extended for FDs.

This was introduced in JuliaLang/julia#52849.

The implementation just needs to forward to Base.checked_power_by_squaring.

Julia 1.4 (JuliaLang/julia#33040) adds a standard interface to specify the rounding mode for integer division div(x, y, ::RoundingMode). FixedDecimals should implement this interface as well, to support different rounding modes for division.

We've wanted to support rounding divisions for a while, anyway, so this a nice motivator.

This was originally discussed in this issue:
JuliaLang/julia#33651

This issue is used to trigger TagBot; feel free to unsubscribe.

If you haven't already, you should update your TagBot.yml to include issue comment triggers.
Please see this post on Discourse for instructions and more details.

If you'd like for me to do this for you, comment TagBot fix on this issue.
I'll open a PR within a few hours, please be patient!

I've recently come to know both projects (https://github.com/JuliaMath/FixedPointNumbers.jl) and I think they're pretty similar, although this project focuses on fixed-point numbers for finances, whereas the other focuses on image processing.

Are the two projects storing fixed-point numbers in a fundamentally different way?
Are you going through different problems?

From what I understand, both projects could really use support. And since you want the same mathematical basis, it seems reasonable to think about joining forces.

It seems you always need to specify how many decimals, e.g. with FixedDecimal{Int8, 2} and that type which is far from optional. Most likely it's not useful enough for money, and when you want to base on Int8 otherwise likely binary fixed point better.

I suggest as a happy medium for your docs, instead of (or have both):

For example, FixedDecimal{Int8, 2} allows you [to a] decimal number with up to 2 fractional digits.

const FixedSafeDecimal = FixedDecimal{Int32, 3}

I intentionally didn't go with Int64, since then you multiply two such numbers you could get FixedDecimal{Int64, 6} and you don't need to check for overflows nor round, and I would like that type to do it by default. It's just an idea for your package, I've been thinking of making my own, and I could do that and wrap yours, in case you don't want to implement this.

You can add and subtract, and then there is a possibility of one extra bit, this overflow, in case you want to check for that, or just go to FixedDecimal{Int64, 3}, note not there ,6. The division is the problem, then I would argue for going to a rational rather than Float64 or either these types.

Because in that case and at least for multiplying you want to put the "genie-back-into-the bottle", and I suggest a round back to FixedSafeDecimal with overflow check postponed until then.

julia> x = FixedDecimal{Int128, 33}(10000)
FixedDecimal{Int128,33}(10000.000000000000000000000000000000000)

julia> y = FixedDecimal{Int128, 38}(0)
FixedDecimal{Int128,38}(0.00000000000000000000000000000000000000)

julia> x == y
ERROR: InexactError: Int128(1000000000000000000000000000000000000000000)
Stacktrace:
 [1] Int128(x::BigInt)
   @ Base.GMP ./gmp.jl:373
 [2] convert
   @ ~/.julia/packages/FixedPointDecimals/Eseyj/src/FixedPointDecimals.jl:313 [inlined]
 [3] _promote
   @ ./promotion.jl:358 [inlined]
 [4] promote
   @ ./promotion.jl:381 [inlined]
 [5] ==(x::FixedDecimal{Int128, 33}, y::FixedDecimal{Int128, 38})
   @ Base ./promotion.jl:449
 [6] top-level scope
   @ REPL[5]:1

This should be not equal rather than InexactError (an implementation detail). Checking representability in == should solve this.

Last year, we made several performance improvements to FixedPointDecimals, and a lot of them used @pure to enforce constant folding.

However, since then (as discussed in last year's JuliaCon talk If Runtime isn't Funtime), I've come to understand that the @pure annotations I've added here are unsafe, because FixedPointDecimals supports arbitrary integer types, and it's not safe to use @pure with user-defined types.

We should revert these annotations before we can make another release.

Long term:

• It would be safe to use @pure if we restricted FixedPointDecimals to the built-in Base.BitInteger types, so we could consider separately defining a version of these functions for the built-in types that are @pure and a non-pure version as the fallback.
• Or we could try to put more work into StagedFunctions.jl, which could be used to provide the same level of performance but currently adds non-trivial compilation time overhead.
• Or we could do some more thinking to see if there's another solution.

For now, we should probably just revert the annotations, at least.

Consider:

using FixedPointDecimals

r = Rational{Int8}(-1//1);
fde = FixedDecimal{Int128,4}(-2.5806);
promote(r, fde)

produces:

ERROR: InexactError: trunc(Int8, -12903)
Stacktrace:
  [1] throw_inexacterror(f::Symbol, #unused#::Type{Int8}, val::Int128)
    @ Core ./boot.jl:612
  [2] checked_trunc_sint
    @ ./boot.jl:634 [inlined]
  [3] toInt8
    @ ./boot.jl:650 [inlined]
  [4] Int8
    @ ./boot.jl:759 [inlined]
  [5] convert
    @ ./number.jl:7 [inlined]
  [6] Rational
    @ ./rational.jl:100 [inlined]
  [7] convert
    @ ./number.jl:7 [inlined]
  [8] convert
    @ ~/.julia/packages/FixedPointDecimals/GFltp/src/FixedPointDecimals.jl:324 [inlined]
  [9] _promote
    @ ./promotion.jl:327 [inlined]
 [10] promote(x::FixedDecimal{Int128, 4}, y::Rational{Int8})
    @ Base ./promotion.jl:350
 [11] top-level scope
    @ REPL[3]:1
 [12] top-level scope
    @ ~/.julia/packages/Infiltrator/R8I9c/src/Infiltrator.jl:632

Thanks to Nick R., David S, Babis, for their help in identifying this.

Once we're satisfied with the repo state, we should tag a release (on @attobot) so that Currencies can properly migrate.

Currently a FixedDecimal value can overflow since internally we are using integer math.

julia> import FixedPointDecimals: FD

julia> reinterpret(FD{Int8,2}, typemax(Int8))
FixedDecimal{Int8,2}(1.27)

julia> ans + reinterpret(FD{Int8,2}, 1)
FixedDecimal{Int8,2}(-1.28)

We should include some kind of system, maybe checked_* operations, so that users can choose how overflow is handled. We definitely do not want to ban the overflow behaviour.

FixedPointDecimals.jl should probably implement Base.big(::FixedDecimal) and Base.big(::Type{<:FixedDecimal}) since other packages may rely on this method. For example, JuliaData/DataFrames.jl#3418 is caused by not implementing this method.

Ref: https://discourse.julialang.org/t/package-compatibility-caps/15301