Oberon Community Platform Forum
December 13, 2019, 03:20:21 AM *
Welcome, Guest. Please login or register.
Did you miss your activation email?

Login with username, password and session length
News:
 
   Home   Help Search Login Register  
Pages: [1] 2
  Print  
Author Topic: HUGEINT division bug  (Read 24257 times)
Alexey
Newbie
*
Posts: 27


« on: January 19, 2009, 11:13:18 AM »

Hi!

when I try to compute c := a DIV b; where all a,b,c are HUGEINT I get a TRAP which is in the enclosure. I used the latest WinAos release.

Best regards,

Alexey

* HUGEINT.bug (2.97 KB - downloaded 441 times.)
Logged
negelef
Administrator
Jr. Member
*****
Posts: 55


« Reply #1 on: January 19, 2009, 12:01:49 PM »

The compiler doesn't really support hugeint multiplication and division. Use Machine.MulH and Machine.DivH for the time being.
Logged
Alexey
Newbie
*
Posts: 27


« Reply #2 on: January 19, 2009, 12:06:19 PM »

Thanks,

Alexey
Logged
Alexey
Newbie
*
Posts: 27


« Reply #3 on: January 19, 2009, 06:32:31 PM »

Anyway there is a problem...

when I tried to compute:

a := 0CD1F42EFH;
b := Machine.DivH(a,60);
c := Machine.MulH(b,60);

I get c = CD1F430C which is bigger than a. It looks like Machine.DivH instead of truncation of LONGREAL FPU result does rounding, because
0CD1F42EFH/60 = 57356300.516.

Regards,

Alexey
Logged
Alexey
Newbie
*
Posts: 27


« Reply #4 on: January 26, 2009, 09:44:08 AM »

Hello,

here is an implementation of HUGEINT multiplication and division for x86 systems based on the code from "AMD Athlon processor x86 Code Optimization Guide". On my Intel PCs it runs 2.4 times faster that current implementation based on the use of FPU, and it gives correct results. FPU based MulH and DivH are very dangerous to use because mantissa in double precision has only 52 bits length, thus for the cases when the result of multiplication or dividend in division require more than 52 bits for their integer representation, you can have an incorrect (rounded) result.

Best regards,

Alexey

* I386.HugeintMulDiv.Mod (3.89 KB - downloaded 468 times.)
Logged
negelef
Administrator
Jr. Member
*****
Posts: 55


« Reply #5 on: January 26, 2009, 10:58:44 AM »

Thanks for the implementation and its evaluation. We will replace the FPU version, but is there a reason why your procedures are marked as inline? What's the performance impact of the alternative non-inlined version? As these procedures contain quite a few instructions, their inlined versions could cause some significant code bloat, couldn't they?
Logged
Alexey
Newbie
*
Posts: 27


« Reply #6 on: January 26, 2009, 01:43:25 PM »

Hi negelef,

I made the procedures inline because Machine.MulH/DivH are inline. In addition I do not know how to access LO/HI of HUGEINT input arguments in non-inline procedures.

Alexey
Logged
negelef
Administrator
Jr. Member
*****
Posts: 55


« Reply #7 on: January 26, 2009, 01:53:29 PM »

Non-inlined procedures written in assembly are called like ordinary procedures. Therefore the CALL instruction on the caller site and the RET instruction on the callee site take over the stack management. Additionally, as the call implicitly creates a new stack frame, the parameters have to be access via the frame base pointer. See e.g. Machine.Fill32 hot to accomplish that.

In inlined versions, programmers have to fake a procedure call by manipulating the stack pointers themselves as there actually is no procedure call at all because its replaced by the assembly code. And since there is no new stack frame, parameters have to be accessed via the stack pointer.
Logged
Alexey
Newbie
*
Posts: 27


« Reply #8 on: January 26, 2009, 03:42:59 PM »

Hi,

here are non-inline assembler procedures. Tests showed decrease of performance by 22% for multiplication and 14% for division, which is not so bad.

Best regards,

Alexey

* I386.HugeintMulDiv.Mod (7.27 KB - downloaded 400 times.)
Logged
negelef
Administrator
Jr. Member
*****
Posts: 55


« Reply #9 on: January 26, 2009, 04:18:38 PM »

Decrease of performance with respect to what? It would be most interesting to see the code used for the benchmarks.
Logged
Alexey
Newbie
*
Posts: 27


« Reply #10 on: January 26, 2009, 05:01:58 PM »

In respect to the performance of inline-procedures. See enclosed test module.

Here are the results for my Intel Quad Q9400 2.6GHz (WinAos)

Machine.MulH:
1560 ms
Hex(HI)=1EABE4BD
Hex(LO)=D7631400

HugeintMulDiv.Mul:
639 ms
Hex(HI)=1EABE4BD
Hex(LO)=D7631388

HugeintMulDiv.Mul1:
796 ms
Hex(HI)=1EABE4BD
Hex(LO)=D7631388

Machine.DivH:
2153 ms
Hex(HI)=00000000
Hex(LO)=0000002C

HugeintMulDiv.Div:
1591 ms
Hex(HI)=00000000
Hex(LO)=0000002B

HugeintMulDiv.Div1:
1841 ms
Hex(HI)=00000000
Hex(LO)=0000002B

Alexey

* HugeintMulDivTest.Mod (3.51 KB - downloaded 463 times.)
« Last Edit: January 26, 2009, 05:07:00 PM by Alexey » Logged
Alexey
Newbie
*
Posts: 27


« Reply #11 on: January 26, 2009, 10:52:55 PM »

Hi!

This is modified test module for testing all branches of the Mul/Div code.

Alexey

* HugeintMulDivTest.Mod (6.76 KB - downloaded 437 times.)
Logged
negelef
Administrator
Jr. Member
*****
Posts: 55


« Reply #12 on: January 27, 2009, 01:18:41 PM »

I just tried to replace the existing version with yours but unfortunately, the system gets quite unstable. It looks like there is a stack problem. At least with the windows version.
Logged
BohdanT
Sr. Member
****
Posts: 271


Life is difficult, but fortunately is short!


WWW
« Reply #13 on: January 27, 2009, 02:28:07 PM »

Quote
It looks like there is a stack problem.

Code:
S.GETREG(S.ESP, spreg);
Log.String("SP= "); Log.Hex(spreg, 0); Log.Ln;
   
I added before and after each FOR-cycle.
ESP - does not change
 Huh
Logged
negelef
Administrator
Jr. Member
*****
Posts: 55


« Reply #14 on: January 27, 2009, 03:11:32 PM »

The stack problem was actually my fault, sorry about that. The non-inlined code now works and is available starting from revision 1897. Thank you very much for the contribution!
Logged
Pages: [1] 2
  Print  
 
Jump to:  

Powered by MySQL Powered by PHP Powered by SMF 1.1.21 | SMF © 2015, Simple Machines Valid XHTML 1.0! Valid CSS!