Problems with `rem` for `Fixed`

[kimikage]

As mentioned in #211 (comment), the rem for Fixed has problems.

FixedPointNumbers.jl/src/fixed.jl

Line 109 in 735b7f9

rem(x::Real, ::Type{Fixed{T,f}}) where {T,f} = Fixed{T,f}(rem(Integer(trunc(x)),T)<<f + rem(Integer(round(rem(x,1)*(one(widen1(T))<<f))),T),0)

I plan to specialize the multiplication for Fixed after the merging PR #213. As part of the specialization, I will improve the rem for Fixed, but since it is not the main topic of the specialization, I opened a separate issue for rem.

Speed performance

Simply put, rem for Fixed is too slow.

julia> x_f32 = rand(Float32, 1000, 1000);

julia> @btime $x_f32 .% Q0f7;
  8.012 ms (2 allocations: 976.70 KiB)

julia> @btime $x_f32 .% N0f8;
  123.300 μs (2 allocations: 976.70 KiB)

Throwing errors

Though this is one of the causes of the slowdown, the rem can throw an error.

julia> 2.0^63 % Q0f7 # Due to `Integer()`
ERROR: InexactError: Int64(9.223372036854776e18)

The rem for Normed prioritizes the speed and allows for inaccurate values to be returned in the overflow.

Unnecessary type conversion

We need the specialized method.

julia> typemax(Q0f63) % Q0f63
ERROR: ArgumentError: Fixed{Int64,63} is a 64-bit type representing 0 values from -1.0 to 1.0; cannot represent 1

[kimikage]

FYI, the behavior of unsafe_trunc on x86 CPUs is described below.

If the value is not representable by T, an arbitrary value will be returned.

https://docs.julialang.org/en/v1/base/math/#Base.unsafe_trunc

On x86 CPUs, a family of (v)cvttsd2si instructions is used to convert floating point numbers to integers. The integer types are signed, and Int32 and Int64 are supported, i.e. the conversion to 8-/16-bit integers is done via Int32. Also, 0x80000000/0x80000000_00000000 is returned in case of overflow.
It is important to note that the range of UInt32 is over the range of Int32. Therefore, unsafe_trunc(UInt32, 1.0) is converted via Int64 instead of Int32. In other words, at the moment, the rem for Normed causes rarely an overflow within the range of practical values. On the other hand, since the current Fixed uses a signed rawtype, unsafe_trunc(Int32, 1.0) does not need to use Int64 in principle. Therefore, the overflow can be a practical problem. (I know that Fixed{Int32} is rarely used, though.)

In addition, the behavior on ARM CPUs is completely different. (cf. #134)

[kimikage]

Fixed by #220.