Recent

Author Topic: Mathematical question  (Read 3341 times)

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Mathematical question
« Reply #45 on: March 02, 2024, 06:55:57 pm »
So if I want to change 1 bit, you suggest to first call Abs() on the value?
Yes, that's correct.
It might seem inefficient, but if you run the code with a timer, the call to Abs adds very little overhead.

Fibonacci

  • Sr. Member
  • ****
  • Posts: 419
Re: Mathematical question
« Reply #46 on: March 02, 2024, 07:04:38 pm »
I was worried that my code might have a bug; and I always welcome bug reports.
So I ran your code, to see what was going on.
After the XOR operation, m = 2147483649
32-bit integer type is signed, and can only accept values between -2,147,483,648 and 2,147,483,647
2147483649 is outside its range, so assigning m to i correctly causes overflow.
If you declare i to be unsigned integer (aka longword, aka uint32), then it works ok, because it can accept values from 0 to 4294967295

Code: Pascal  [Select][+][-]
  1. var
  2.   i: integer;
  3.   m: Multi_Int_XV;
  4. begin
  5.   writeln('xor on integer = ok');
  6.   i := 1;
  7.   writeln(binstr(i, 32), ' = ', i);
  8.   i := i xor (1 shl 31);
  9.   writeln(binstr(i, 32), ' = ', i);
  10.  
  11.   writeln;
  12.  
  13.   writeln('xor on integer then casted to Multi_Int_XV = ok');
  14.   i := 1;
  15.   m := i;
  16.   writeln(binstr(integer(m), 32), ' = ', string(m));  
  17.   i := i xor (1 shl 31);
  18.   m := i;
  19.   writeln(binstr(integer(m), 32), ' = ', string(m));
  20.  
  21.   writeln;
  22.  
  23.   writeln('xor on Multi_Int_XV = overflow on cast to integer');
  24.   m := 1;    
  25.   writeln(binstr(integer(m), 32), ' = ', string(m));
  26.   m := m xor (1 shl 31);
  27.   //writeln(binstr(integer(m), 32), ' = ', string(m)); // integer(m) = overflow
  28.   // because of overflow, lets cast it to int64
  29.   writeln(binstr(int64(m), 32), ' = ', string(m)); // high 32 bits are 0s
  30.  
  31.   writeln;
  32.  
  33.   // is the value the same as integer?
  34.   writeln('value correct? ', int64(m) = i, ', ', int64(m), ' vs ', i);    
  35.   writeln('bits the same? ', binstr(i, 64) = binstr(int64(m), 64));
  36.   writeln('i bits = ', binstr(i, 64));
  37.   writeln('m bits = ', binstr(int64(m), 64));
  38.  
  39.   writeln;
  40.   writeln('------------------------');
  41.   writeln;
  42.  
  43.   writeln('negative value, test on integer');
  44.   i := -1;
  45.   i := i xor (1 shl 31);
  46.   writeln('i = ', i, ', bits = ', binstr(i, 32));
  47.  
  48.   writeln('negative value, test on Multi_Int_XV');
  49.   m := -1;
  50.   //m := m xor (1 shl 31); // failed: Raise EInterror.create('Bitwise operation on negative value');

Code: Pascal  [Select][+][-]
  1. xor on integer = ok
  2. 00000000000000000000000000000001 = 1
  3. 10000000000000000000000000000001 = -2147483647
  4.  
  5. xor on integer then casted to Multi_Int_XV = ok
  6. 00000000000000000000000000000001 = 1
  7. 10000000000000000000000000000001 = -2147483647
  8.  
  9. xor on Multi_Int_XV = overflow on cast to integer
  10. 00000000000000000000000000000001 = 1
  11. 10000000000000000000000000000001 = 2147483649
  12.  
  13. value correct? FALSE, 2147483649 vs -2147483647
  14. bits the same? TRUE
  15. i bits = 0000000000000000000000000000000010000000000000000000000000000001
  16. m bits = 0000000000000000000000000000000010000000000000000000000000000001



So if I want to change 1 bit, you suggest to first call Abs() on the value?
Yes, that's correct.
It might seem inefficient, but if you run the code with a timer, the call to Abs adds very little overhead.

Code: Pascal  [Select][+][-]
  1. var
  2.   i: integer;
  3. begin
  4.   i := -123;
  5.   writeln('bits                   = ', binstr(i, 32));
  6.   i := -123;
  7.   i := i xor (1 shl 31);
  8.   writeln('bits xored without ABS = ', binstr(i, 32));
  9.   i := -123;
  10.   i := abs(i);
  11.   i := i xor (1 shl 31);
  12.   writeln('bits xored    with ABS = ', binstr(i, 32));

Code: Pascal  [Select][+][-]
  1. bits                   = 11111111111111111111111110000101
  2. bits xored without ABS = 01111111111111111111111110000101
  3. bits xored    with ABS = 10000000000000000000000001111011

You see what Abs() is doing?

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Mathematical question
« Reply #47 on: March 02, 2024, 07:15:37 pm »
Of course if I first call Abs() on the value, it will work, but the value will be completely wrong.
You must code it like this:
Code: Pascal  [Select][+][-]
  1. var m:Multi_Int_XV;
  2. // m is set to some unknown value by other code
  3. if (negative(m)) then m := -(ABS(m) xor (1 shl 31))
  4. else m := (m xor (1 shl 31));
  5.  
BTW... I just realised that I somehow "lost" the Negative function from the library code. I've just fixed that in the last 3 mins. Please download the latest version of the code to get Negative functions back.
The following will still work with the previous version:
Code: Pascal  [Select][+][-]
  1. if (m.negative) then m := -(ABS(m) xor (1 shl 31))
  2. else m := (m xor (1 shl 31));
Apologies for that mistake.
« Last Edit: March 02, 2024, 07:19:38 pm by ad1mt »

Fibonacci

  • Sr. Member
  • ****
  • Posts: 419
Re: Mathematical question
« Reply #48 on: March 02, 2024, 07:21:51 pm »
Is that mentioned in your documentation? If one wants to use this unit, one must first read it all carefully cos it doesnt work as expected :) The expected behavior in this xoring is to do overflow. Also exceptions when doing bitwise operations on negative values are unexpected.

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Mathematical question
« Reply #49 on: March 02, 2024, 07:53:42 pm »
Is that mentioned in your documentation?
@Fibonacci
Thanks for reminding me...
I've just realised that since clarifying/changing how to do bitwise operations on negative values in this thread, I forgot to update the documentation. I will update it very shortly.

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Mathematical question
« Reply #50 on: March 03, 2024, 11:40:25 am »
@Fibonacci
I've changed my mind.
If I had enforced this from the beginning, my original division algorithm would not have been allowed!

So I'm going to remove all the restrictions on bitwise operations.
I will also document the internal structure of the big integers, so that programmers can decide for themselves whether/how to use the bitwise operators.

The new version is not ready yet, but hopefully will be ready by the end of today (Sunday).

ad1mt

  • Full Member
  • ***
  • Posts: 199
    • Mark Taylor's Home Page
Re: Mathematical question
« Reply #51 on: March 03, 2024, 01:31:02 pm »
Here is my proposed logic for deciding the sign of the result when negative values are used in bitwise operations:

XOR - if the signs are different, the result is negative, otherwise the result is positive
OR - if the both signs are negative, the result is negative, otherwise the result is positive
AND - if the both signs are negative, the result is negative, otherwise the result is positive
NOT - if the sign is positive, the result is negative, otherwise the result is positive

I propose to "give preference" to positive values in the result. This has resulted in a logical inconsistency between AND & OR operators.

Maybe the behaviour of the AND & OR operators, should be "opposite" to each other, as follows...

either
OR - if the both signs are negative, the result is negative, otherwise the result is positive
AND - if the both signs are positive, the result is positive, otherwise the result is negative
(a positive sign is considered to a positive "value")

or
OR - if the both signs are positive, the result is positive, otherwise the result is negative
AND - if the both signs are negative, the result is negative, otherwise the result is positive
(a negative sign is considered to a positive "value")

Alternative suggestions are welcome.
« Last Edit: March 08, 2024, 12:32:38 am by ad1mt »

 

TinyPortal © 2005-2018