help-smalltalk
[Top][All Lists]
Advanced

[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

[Help-smalltalk] Re: [PATCH] Fraction and Integer asFloat: answer neares


From: nicolas cellier
Subject: [Help-smalltalk] Re: [PATCH] Fraction and Integer asFloat: answer nearest floating point
Date: Sun, 28 Jan 2007 22:45:51 +0100
User-agent: Thunderbird 1.5.0.4 (X11/20060516)

Paolo Bonzini a écrit :
nicolas cellier wrote:
Hello,

here are some enhancements that should answer nearest floating point value when converting LargeInteger and Fraction asFloat.

For LargePositiveInteger, i have two versions, one un-optimized and one optimized for gst.

Which is the optimized one (the one whose source does not mention checkIfLowBitGreaterThan: n, or the other)?

Paolo

The optimized one is in file named 'LargePositiveIntegerOptimized.asFloat:.st' and it calls #checkIfLowBitGreaterThan:

This last message is most of the optimization.
We just need to know if some trailing bits are truncated or not in order to do the rounding.

Non optimized version is using bit operations with masks like traditional Smalltalk patterns (bitShift: and bitAnd:). This is efficient for SmallIntegers. Unfortunately, in our case this creates a lot of intermediary LargePositiveInteger objects and is slow.

Optimized version do this without creating any new LargePositiveInteger, just iterating on bits with bitAt: test, which is further accelerated by testing bytes with digitAt: tests when number of bits > 8 (and would be further optimized in a primitive with 16, 32 or 64 bits by 64 bits tests...).

Also, non zero bit search is stopped as soon as a non zero bit is found.

I am quite sure that a more general message named #lowBit would do almost as well and could be used in other algorithms.

LargePositiveInteger>>lowBit
    "answer the index of least significant non zero bit.
     answer 0 if receiver is zero.
     LSB is indexed 1."

    1 to: self size do: [:i | | lowBit |
        lowBit := (self digitAt: i) lowBit.
        lowBit = 0 ifFalse: [(î-1)*8 + lowBit]].

    ^0

SmallInteger>>lowBit
    "same as above.
    Note: there are faster implementations to be found for sure"

    | shifted lowBit |
    self = 0 ifTrue: [^0].
self < 0 ifTrue: [self error: 'i do not know how to handle this one... and i do not much like negative integer highBit implementation neither'].
    shifted := self.
    lowBit := 1.
    [(shifted bitAnd: 1) = 0] whileTrue:
        [shifted := shifted bitShift: -1.
         lowBit := lowBit+1}.
    ^lowBit


Nicolas





reply via email to

[Prev in Thread] Current Thread [Next in Thread]