# [Vm-dev] vm problem on cog and stack spur

Nicolas Cellier nicolas.cellier.aka.nice at gmail.com
Sun Mar 27 22:09:37 UTC 2016

```OK, I think I get it.
The problem lies in:

"Correct overestimate of q.
Max of 2 iterations through loop -- see Knuth vol. 2"
j < 3
ifTrue: [r3 := 0]
ifFalse: [r3 := pRem at: j - 3].

[(t < hi
or: [t = hi and: [r3 < lo]])
ifTrue:
["i.e. (t,r3) < (hi,lo)"
q := q - 1.
lo < dnh
ifTrue:
[hi := hi - 1.
lo := lo + 16r100 - dnh]
ifFalse:
[lo := lo - dnh].
cond := hi >= dh]
ifFalse: [cond := false].
cond]
whileTrue: [hi := hi - dh]].

What happens here is that hi may become negative.
But since I declared it unsigned, t<hi and cond := hi >= dh remains false
quite a long time and the quotient q is decremented way too many times...

Here we divide (r1,r2,r3,...) by (dh,dnh,...)
we are trying to guess q based on 2 limbs
(r1,r2) = q*dh + t    that is   (r1,r2-t) = q*dh
(hi,lo) =q*dnh

Thus q*(dh,dnh)=(r1,r2-t+hi,lo)

If t<hi then q*(dh,dnh) is greater than (r1,r2) and we have an overestimate
of q
Same if t=hi and lo<r3.

Here we have the tricky case when t=0, r3=0 and lo>0, and hi=dnh+1
In the first loop, h gets decremented, thus hi=dnh.
Then it goes to 0, and gets decremented a second time...

The same algorithm is used with 32bits limbs, so it may also happen in my
own VM branch. I believe it must be even rarest an event though (2^32
possible values for hi makes hi=dnh+1 less probable than with 2^8
combinations).

I will fix it tonight or tomorrow.

2016-03-27 19:03 GMT+02:00 Nicolas Cellier <
nicolas.cellier.aka.nice at gmail.com>:

> Thanks David.
>
> By running the snippet, instrumenting erf, printing each and every
> intermediate value to a text file, and diffing:
> {
> (10 asArbitraryPrecisionFloatNumBits: 33) erf.
> (10 asArbitraryPrecisionFloatNumBits: 34) erf.
> }
>
> I reduced the failing test to:
>
>  a :=
> 1598335257761788022467377781654101148543282249044465229239888363328190330275719997501596724768507889233831388734160190922469363547795602076820594918.
> b := 49612.
> self assert: a - ((a quo: b)*b) < b
>
> So it must be some nasty sign promotion (or lack of?) in division.
> Normally, this could be simulated, but with signedness, I'm never sure,
> maybe my next step will be a breakpoint in xcode/gdb...
>
>
> Curiously, (a rem: b) is correct !
>
> 2016-03-27 17:36 GMT+02:00 David T. Lewis <lewis at mail.msen.com>:
>
>>
>> I confirm the same results for your ArbitraryPrecisionFloat example below,
>> testing on Linux with a 64 bit interpreter VM and 32 bit image.
>>
>>   Image
>>   -----
>>   /home/lewis/squeak/Squeak4.6/squeak.37.image
>>   Squeak4.6
>>   latest update: #15723
>>   Current Change Set: Unnamed2
>>   Image format 6504 (32 bit)
>>
>>   Virtual Machine
>>   ---------------
>>   /usr/local/lib/squeak/4.15.4-3634/squeakvm
>>   Squeak4.5 of 10 December 2015 [latest update: #1195]
>>   Unix built on Mar 25 2016 13:27:51 Compiler: 4.9.2
>>   platform sources revision 3634
>>   VMMaker versionString 4.15.4
>>
>> Dave
>>
>>
>> On Sun, Mar 27, 2016 at 03:25:58PM +0200, Nicolas Cellier wrote:
>> >
>> > Hi Levente, thank you.
>> > Here is a follow up:
>> >
>> > I was able to reproduce the same symptom on the classical interpreter
>> VM.
>> > <rant> It's just that for MacOSX, there is no recent VM available, and
>> that
>> > the MacOS build is somehow abandonware, so it took much more time than
>> > necessary :( </rant>
>> >
>> > So the changes that have been integrated on Interpreter Vm in july 2014
>> and
>> > that I thought correct were not.
>> > It's certainly related to a LargeInteger plugin primitive.
>> > Those are triggered when nbits of magnitude > 64.
>> > (otherwise, <= 64 bits, the LargeInteger numbered primitives do their
>> job).
>> >
>> > Now the job is to produce/isolate an elementary failing LargeInteger
>> test.
>> > But you need to generate the VM from VMMaker.oscog head for COG/STACK
>> > V3/SPUR 32/64 bits
>> > or use a sufficiently recent interpreter VM (> july 2014) to trigger
>> such
>> > failure.
>> >
>> >
>> > --------------------------------------------
>> >
>> > Here is my starting point:
>> >
>> > If you load ArbitraryPrecisionFloat and Tests from
>> > http://www.squeaksource.com/ArbitraryPrecisionFl
>> > then you'll see this strange pattern:
>> >
>> > (53 to: 70) collect: [:i |
>> >     i -> (10 asArbitraryPrecisionFloatNumBits: i) erf ]
>> >
>> > numBits: 53) .
>> > numBits: 57) .
>> > numBits: 61) .
>> > numBits: 65) .
>> > readStream numBits: 69) .
>> >
>> > The value seems incorrect every four numbits
>> > The exact value is near 1- 2.0e-45, and given the insufficient precision
>> > requested, the result should be rounded to 1.
>> > We can confirm with online high precision erf calculator like found for
>> > example with http://keisan.casio.com/exec/system/1180573449
>> >
>> > Or we can check with
>> > (10 asArbitraryPrecisionFloatNumBits: 200) erf (ArbitraryPrecisionFloat
>> '0.999999999999999999999999999999999999999999997911512416237455'
>> >
>> > -----------------------------
>> >
>> > Note that when I change the LargeInteger digitLength to 32bits instead
>> of 8
>> > (my own VM branch) then the problem magically disappear.
>> >
>> > I plan to introduce these change in the VMMaker.oscog, so I can as well
>> > ignore the problem and proceed, however I much prefer to isolate it, and
>> > understand it for gain of knowledge :)
>> >
>> >
>> > 2016-03-27 4:27 GMT+02:00 Levente Uzonyi <leves at caesar.elte.hu>:
>> >
>> > >
>> > > Hi Nicolas,
>> > >
>> > > If you give us a bit more detailed instructions about what to test,
>> then
>> > > we might be able to help you get this sorted out.
>> > >
>> > > Levente
>> > >
>> > >
>>
>>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.squeakfoundation.org/pipermail/vm-dev/attachments/20160328/eb64f98b/attachment.htm
```