[Python-ideas] Re: Exact decimal multiplication and division operations
On Fri, 9 Oct 2020 at 23:41, Tim Peters wrote:
> But the decimal spec takes a different approach, which Python's docs
> don't explain at all: the otherwise-mysterious ROUND_05UP rounding
> mode. Quoting from the spec:
>
> http://speleotrove.com/decimal/damodel.html
> ...
> The rounding mode round-05up permits arithmetic at shorter
> lengths to be emulated in a fixed-precision environment without
> double rounding. For example, a multiplication at a precision of 9
> can be effected by carrying out the multiplication at (say) 16
> digits using round-05up and then rounding to the required length
> using the desired rounding algorithm.
>
> In your original example, 1.01 * 1.46 rounds to 4-digit 1.474 under
> ROUND_05UP. and then `quantize()` can be used to round that back to 1,
> 2, or 3 digits under any rounding mode you like.
>
> Or, with your last example,
>
> >>> with decimal.localcontext() as ctx:
> ... ctx.rounding = decimal.ROUND_05UP
> ... r = D('1.01')*D('1.46')
> >>> r
> Decimal('1.474')
> >>> r.quantize(D('.01'))
> Decimal('1.47')
And can't be this the default of decimal? For what I know, this is the
default of BigDecimal in Java:
> public BigDecimal multiply(BigDecimal multiplicand)
>
> Returns a BigDecimal whose value is (this × multiplicand), and whose scale is
> (this.scale() + multiplicand.scale()).
> Parameters:multiplicand - value to be multiplied by this
> BigDecimal.Returns:this * multiplicand
>
>
> public BigDecimal multiply(BigDecimal multiplicand,
>MathContext mc)
>
> Returns a BigDecimal whose value is (this × multiplicand), with rounding
> according to the context settings.
Example online: http://tpcg.io/5axMxUQb
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/VPAV3T2XN4DARL5RNBNCYFP5IP4BGYAX/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Exact decimal multiplication and division operations
On Thu, 8 Oct 2020 at 16:59, Random832 wrote:
>
> I was making a "convert Fraction to Decimal, exactly if possible" function
> and ran into a wall: it's not possible to do some of the necessary operations
> with exact precision in decimal:
>
> - multiplication
> - division where the result can be represented exactly [the divisor is an
> integer whose prime factors are only two and five, or a rational number whose
> numerator qualifies]
>
> I assume there's some way around it that I haven't spent enough time to
> figure out [create a temporary context with sufficint digits for
> multiplication, and work out the reciprocal power of 10 by hand to use this
> multiplication to implement division], but I feel like these exact operations
> should be supported in the standard library.
It should be possible to do this by bounding the number of digits
required for an exact operation. We can count the number of digits in
the mantissa of a Decimal like this:
In [100]: num_digits = lambda d: len(d.as_tuple().digits)
In [101]: num_digits(Decimal('12.34'))
Out[101]: 4
If d3 = d1 * d2 then num_digits(d3) <= num_digits(d1) + num_digits(d2)
so we can easily bound the number of digits needed for an exact
multiplication. We can create a context for a number of digits and use
it for multiplication like so:
In [106]: ctx = getcontext().copy()
In [107]: ctx.prec = 4
In [108]: ctx.multiply(Decimal('991'), Decimal('12'))
Out[108]: Decimal('1.189E+4')
So then the result without rounding is:
In [109]: d2 = Decimal('991')
In [110]: d3 = Decimal('12')
In [111]: ctx.prec = num_digits(d2) + num_digits(d3)
In [112]: ctx.multiply(Decimal('991'), Decimal('12'))
Out[112]: Decimal('11892')
For division it is a little more complicated. You say the division is
exact so for some nonnegative integer k and integer n the divisor is
either:
a) 2**k * 10**n
b) 5**k * 10**n
Dividing/multiplying by 10 does not require any increase in precision
but dividing by 2 or 5 requires at most 1 extra digit so:
In [114]: d = Decimal('123.4')
In [115]: ctx.prec = num_digits(d) + 1
In [116]: ctx.divide(d, 2)
Out[116]: Decimal('61.7')
Of course to make that usable you'll need to calculate k.
Also you'll want to set the Inexact trap:
In [119]: ctx.traps[Inexact] = True
In [120]: ctx.divide(d, 3)
---
Inexact Traceback (most recent call last)
in
> 1 ctx.divide(d, 3)
Inexact: []
For smallish Decimals it will probably be faster to convert to
Rational but for sufficiently large exponents Rational will be very
slow.
--
Oscar
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/K7NHDVO34TNGFQUJQ2CFNWGKMFPYPDNE/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Exact decimal multiplication and division operations
[Random832 ]
> My suggestion was for a way to make it so that if an exact result is
> exactly representable at any precision you get that result, with
> rounding only applied for results that cannot be represented exactly
> regardless of precision.
That may have been the suggestion in your head ;-) , but - trust me on
this - it's taken a long time to guess that from what you wrote.
Again, you could have saved us all a world of troubles by giving
concrete examples.
What you wrote just now adds another twist: apparently you DO want
rounding in some cases ("results that cannot be represented exactly
regardless of precision"). The frac2dec function I suggested
explicitly raised a ValueError in that case instead, and you said at
the time that function would do what you wanted.
> It seems like this is incompatible with the design of the decimal module, but
> it's ***absolutely*** untrue that "if an exact result is exactly
> representable,
> then that's the result you get", because *the precision is not part of the
> representation format*.
Precision certainly is part of the model in the standards the decimal
module implements. The decimal module slightly extends the standards
by precisely defining what happens for basic operations when mixing
operands of different precisions: the result is as if computed to
infinite precision, then rounded once at the end according to the
context rounding mode, to the context precision.
> What threw me off is the fact that there is a single type that represents
> an unlimited number of digits, rather than separate types for each precision.
> I don't think that feature is shared with IEEE,
RIght, the standards don't define mixed-precision arithmetic, but
`decimal` does.
> and it creates a philosophical question of interpretation [the answer of which
> we clearly disagree on] of what it means for a result to be "exactly
> representable",
> which doesn't exist with the IEEE fixed-length formats.
No, it does: for virtually every operation, apart from the
constructor, "exactly representable" refers to the context's precision
setting. If you don't believe that, see how and when the "inexact"
flag gets set. It's the very meaning of the "inexact" flag that "the
infinitely precise result was not exactly representable (i.e.,
rounding lost some information)". It's impossible to divorce the
meaning of "inexact" from the context precision.
> At this point, doing the math in Fractions and converting back and forth
> to Decimal as necessary is probably good enough, though.
I still don't get it. The frac2dec function I wrote appeared to me to
be 99.9% useless, since, as already explained, there's nothing you can
_do_ with the result that doesn't risk rounding away its digits. For
that reason, this feels like an extended "XY problem" to me.
>>> Incidentally, I also noticed the procedure suggested by the documentation
>>> for
>>> doing fixed point arithmetic can result in incorrect double rounding in
>>> some situations:
>>> >>> (D('1.01')*D('1.46')).quantize(TWOPLACES) # true result is 1.4746
>>> Decimal('1.48')
>> Are you using defaults, or did you change something? Here under
>> 3.9.0, showing everything:
> This was with the precision set to 4, I forgot to include that.
A rather consequential omission ;-)
> With default precision the same principle applies but needs much longer
> operands to demonstrate. The issue is when there is a true result that
> the last digit within the context precision is 4, the one after it is 6, 7, 8,
> or 9, and the one before it is odd. The 4 is rounded up to 5, and that 5 is
> used to round up the previous digit.
>
> Here's an example with more digits - it's easy enough to generalize.
>
> >>> ctx.prec=28
> >>> (D('1.01')*D('1.46')).quantize(D('.01'))
> Decimal('1.48')
> >>> ctx.prec=29
> >>> (D('1.01')*D('1.46')).quantize(D('.01'))
> Decimal('1.47')
>
> The true result of the multiplication here is 1.4746,
> which requires 29 digits of precision
>
> [and, no, it's not just values that look like 99 and 01, but a brute
> force
> search takes much longer for 15-digit operands than 3-digit ones]
Understood. The docs are only answering "Once I have valid two place
inputs, how do I maintain that invariant throughout an application?".
They don't mention double rounding, and I don't know whether the doc
author was even aware of the issue.
I argued with Mike Cowlishaw about it when the decimal spec was first
being written, pushing back against his claim that it naturally
supported fixed-point (as well as floating-point) decimal arithmetic.
Precisely because of possible "double rounding" surprises when trying
to use the spec to _emulate_ fixed point.
You can worm around it by using "enough" extra precision, but I don't
recall the precise bounds needed. For binary arithmetic, and + - * /,
if you compute to p bits fir
[Python-ideas] Re: Exact decimal multiplication and division operations
On Thu, Oct 8, 2020, at 16:07, Tim Peters wrote:
> See above. It's very much a feature of the IEEE 754/854 standards (of
> which family Python's decimal model is a part) that if an exact
> result is exactly representable, then that's the result you get.
My suggestion was for a way to make it so that if an exact result is exactly
representable at any precision you get that result, with rounding only applied
for results that cannot be represented exactly regardless of precision. It
seems like this is incompatible with the design of the decimal module, but it's
***absolutely*** untrue that "if an exact result is exactly representable, then
that's the result you get", because *the precision is not part of the
representation format*.
What threw me off is the fact that there is a single type that represents an
unlimited number of digits, rather than separate types for each precision. I
don't think that feature is shared with IEEE, and it creates a philosophical
question of interpretation [the answer of which we clearly disagree on] of what
it means for a result to be "exactly representable", which doesn't exist with
the IEEE fixed-length formats.
At this point, doing the math in Fractions and converting back and forth to
Decimal as necessary is probably good enough, though.
> But that's apparently not what you're asking for.
>
> > ...
> > Incidentally, I also noticed the procedure suggested by the documentation
> > for
> > doing fixed point arithmetic can result in incorrect double rounding in
> > some situations:
> > >>> (D('1.01')*D('1.46')).quantize(TWOPLACES) # true result is 1.4746
> > Decimal('1.48')
>
> Are you using defaults, or did you change something? Here under
> 3.9.0, showing everything:
This was with the precision set to 4, I forgot to include that. With default
precision the same principle applies but needs much longer operands to
demonstrate. The issue is when there is a true result that the last digit
within the context precision is 4, the one after it is 6, 7, 8, or 9, and the
one before it is odd. The 4 is rounded up to 5, and that 5 is used to round up
the previous digit.
Here's an example with more digits - it's easy enough to generalize.
>>> ctx.prec=28
>>> (D('1.01')*D('1.46')).quantize(D('.01'))
Decimal('1.48')
>>> ctx.prec=29
>>> (D('1.01')*D('1.46')).quantize(D('.01'))
Decimal('1.47')
The true result of the multiplication here is 1.4746,
which requires 29 digits of precision
[and, no, it's not just values that look like 99 and 01, but a brute
force search takes much longer for 15-digit operands than 3-digit ones]
> > I didn't know that Decimal supported E notation in the constructor, so I
> > thought
> > I would have to multiply or divide by a power of ten directly [which would
> > therefore have to be rounded]... going through the string constructor seems
> > extremely inefficient and inelegant, though,
>
> Not at all! Conversion between decimal strings and decimal.Decimal
> objects is close to trivial. It's straightforward and linear-time (in
> the number of significant digits).
I think for some reason I'd assumed the mantissa was represented as a binary
number, since the .NET decimal format [which isn't arbitrary-precision] does
that I should probably have looked over the implementation more before jumping
in.
> > I'd like a way to losslessly multiply or divide a decimal by a power of ten
> > at least... a sort of decimal equivalent to ldexp.
>
> Again, without concrete examples, that's clear as mud to me.
Er, in this case the conversion of fraction to decimal *is* the concrete
example, it's a one-for-one substitution for the use of the string constructor:
ldexp(n, -max(e2, e5)) in place of D(f"{n}E-{max(e2, e5}").
___
Python-ideas mailing list -- python-ideas@python.org
To unsubscribe send an email to python-ideas-le...@python.org
https://mail.python.org/mailman3/lists/python-ideas.python.org/
Message archived at
https://mail.python.org/archives/list/python-ideas@python.org/message/AA5P4PPBAPA66WLWQP4ZN4CM4ZMARNIN/
Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Introducing array shape in function declaration
Hello! I want to discuss one feature for handful working with shapes of array-like objects. If we want to pass arrays to function we can declare their sizes directly with argument declaration: ``` def foo(a[m, n], b[n]): for i in range(m): for j in range(n): a[i, j] = b[j] ``` Will be equivalent to ``` def foo(a, b): m, n = a.__shape__() n_b = b.__shape__() if n_b != n: raise ShapeNotValidException() ... ``` Objects should implement `__shape__` magic method to use this syntax. Shapes automatically introduced to variables and checked. Also we can allow more complex checks, e.g.: ``` def bar(a[2,...]): ... ``` will check that first dimension of passed array equals to 2. Or: ``` def bar(a[n], b[2*n]): # checks that a.__shape__()[0] == 2 * b.__shape__()[0] ... ``` ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/HCVVDA4HRD6ASIJMRT4IRXSSVF3X2PL2/ Code of Conduct: http://python.org/psf/codeofconduct/
[Python-ideas] Re: Exact decimal multiplication and division operations
On Thu, 8 Oct 2020 at 22:10, Tim Peters wrote: > Again, the concept of a _fixed_ (albeit user-settable) working > precision is deep in the module's bones. That is, for what I know, how also BigDecimal in Java works... and float in any architecture. ___ Python-ideas mailing list -- python-ideas@python.org To unsubscribe send an email to python-ideas-le...@python.org https://mail.python.org/mailman3/lists/python-ideas.python.org/ Message archived at https://mail.python.org/archives/list/python-ideas@python.org/message/N77ZZEV7QUP3DNATAKSAAUVD3KSVZKLZ/ Code of Conduct: http://python.org/psf/codeofconduct/
