8

I am writing a simple BigInteger type in Delphi. This type consist of an array of unsigned 32 bit integers (I call them limbs), a count (or size) and a sign bit. The value in the array is interpreted as absolute value, so this is a sign-magnitude representation. This has several advantages, but one disadvantage.

The bitwise operations like and, or, xor and not have two's complement semantics. This is no problem if both BigIntegers have positive values, but the magnitudes of negative BigIntegers must be converted to two's complement by negation. This can be a performance problem, since if we do, say

C := -A and -B;

then I must negate the magnitudes of A and B before the and operation can be performed. Since the result is supposed to be negative too, I must negate the result too to get a positive magnitude again. For large BigIntegers, negating up to three values can be a considerable performance cost.

Mind you, I know how to do this and the results are correct, but I want to avoid the slowness caused by the necessary negations of large arrays.

I know of a few shortcuts, for instance

C := not A;

can be achieved by calculating

C := -1 - A;

which is what I do, and the result is fine. This makes not as performant as addition or subtraction, since it avoids the negation before (and after) the operation.

Question

My question is: are there similar laws I can use to avoid negating the magnitudes of "negative" BigIntegers? I mean something like the calculation of not by using subtraction?

I mean simple or not-so-simple laws like

not A and not B = not (A or B) // = is Pascal for ==
not A or not B = not (A and B)

but then for -A and/or -B, etc. I do know that

(-A and -B) <> -(A or B) // <> is Pascal for !=

is not true, but perhaps there is something similar?

I simply can't find any such laws that relate to negative values and bitwise operations, if they exist at all. Hence my question.

Community
  • 1
  • 1
Rudy Velthuis
  • 28,387
  • 5
  • 46
  • 94
  • How does libgmp tackle this? – David Heffernan Aug 30 '15 at 15:01
  • @DavidHeffernan: I have no idea, actually. I do not want to peek, that would be cheating. But I'm afraid they do the same as I do: turn the magnitudes into two's complement, perform the operation and then, if necessary, turn it back to sign-magnitude (only necessary for negative results). I know that I could use libgmp, but I want to learn from doing it myself. FWIW, converting from sign-magnitude to two's complement is symmetrical, so the same routine can be used to convert forth and back. – Rudy Velthuis Aug 30 '15 at 15:08
  • 1
    If you want to learn for yourself, why are you asking? You are asking because you want to learn from others. – David Heffernan Aug 30 '15 at 15:13
  • 1
    I want to learn from others about the logics. I want to learn and apply what I have learned myself. What I have works, and works well. But I am always willing to improve. As I said, there is nothing wrong with finding knowledge, but simply copying the (GPL-ed) code of others is not what I want. – Rudy Velthuis Aug 30 '15 at 15:46
  • I'm not suggesting that you **copy** GPL code. – David Heffernan Aug 30 '15 at 15:47
  • @DavidHeffernan: telling me to use the code of others, or to look at theirs, does not really help me solve my problem. I am asking what I ask because I want to learn how to do it myself. OK? That is the same reason I wrote a Decimal type. I wanted to know how hard it is to write a (decimal) floating point type. – Rudy Velthuis Aug 30 '15 at 15:48
  • 1
    I repeat, I am not telling you to use the code of others. What made you think I said that? – David Heffernan Aug 30 '15 at 15:52
  • I actually don't know what you are telling me. I do know that it does not help me learn what I want to learn: laws that help me simplify my code. FWIW, I don't even know if GMP uses sign-magnitude. – Rudy Velthuis Aug 30 '15 at 15:55
  • You don't have to copy code. You can read it and understand it. – David Heffernan Aug 30 '15 at 15:58
  • I want to have a "clean room" implementation. I won't have that if I look at other people's implementations. – Rudy Velthuis Aug 30 '15 at 15:59
  • 1
    If you want a clean implementation then do it yourself. If you ask others to tell you how to do it, how do you know you are still clean? Suppose I read another library, work out how it solves these issues, and then write an answer here. How does that differ from you reading the code? – David Heffernan Aug 30 '15 at 16:00
  • I am asking others about the logic that applies, not about any implementation details. I actually hate to be driven into the defensive about *why* I want to know this simple question about logic and mathematics. And I dislike to be downvoted too. This is really something that can't be found anywhere, so I really wonder what is wrong with the question. – Rudy Velthuis Aug 30 '15 at 16:12
  • Exactly. It's possible to read code and understand the algorithms that underpin the code. That's all I am saying. – David Heffernan Aug 30 '15 at 16:15
  • I don't want to read other people's code. I want to understand the logic/maths that apply, if any. No more. – Rudy Velthuis Aug 30 '15 at 16:16
  • In that case you've probably asked on the wrong site because this site is for programming questions. You are asking a maths question. – David Heffernan Aug 30 '15 at 16:19
  • @DavidHeffernan: In other words, there is a big difference between someone teaching me about assembler and adding with a carry, which is general knowledge, and someone telling me how to use assembler to implement a BigInteger or Decimal implementation. I want the general knowledge, if there is any. – Rudy Velthuis Aug 30 '15 at 16:21
  • I have a specific programming question. I think this site is right. But the only comments I get are doubts about *why* I want to do this,. – Rudy Velthuis Aug 30 '15 at 16:23
  • You aren't asking about programming. You are asking about maths and algorithms. – David Heffernan Aug 30 '15 at 16:25
  • FWIW, I am asking about bit manipulation in Delphi, as tagged. – Rudy Velthuis Aug 30 '15 at 16:26
  • One thing I don't understand is why you mention `(not A) and (not B) = not (A or B)`. That's a logical identity. But your question concerns bitwise operations. In fact the more I read your question the less clear it becomes. – David Heffernan Aug 30 '15 at 16:28
  • "I want to understand the logic/maths that apply, if any." "I am asking about bit manipulation in Delphi." Which is it? Are you looking for a theoretical mathematical answer, or an answer with code and implementation in a specific language. – David Heffernan Aug 30 '15 at 16:31
  • 1
    @DavidHeffernan, it's really clear. Rudy want to know why the logical operations work the way they do, rather than copy paste. So it's a question about boolean algabra and the nitty gritti of 2's complement negatives. Nothing complicated really. – Johan Aug 30 '15 at 16:31
  • @Johan It's not clear to me. I don't see how those logical identities relate to bitwise operations. – David Heffernan Aug 30 '15 at 16:33
  • 2
    you can use 2's complement for the BigInteger. The most significant limb will be of a 2's complement signed type and the remaining limbs' type is unsigned. It's much easier to implement as most operations would be the same for signed and unsigned types – phuclv Aug 30 '15 at 16:48
  • I can use two's complement, but most of the code I designed assumes an unsigned magnitude. I thought long and hard about this, and found that sign-mangitude is the best for my purposes. The only problem are the bitwise operators. – Rudy Velthuis Aug 30 '15 at 17:05
  • @DavidHeffernan: `not A and not B = not (A or B)` applies to bitwise manipulation too. You can do the same with two integers. So I am asking about bit manipulation (*bitwise* `and`, `or` and `xor`), which does of course rely on simple boolean logic. What is so hard to understand? – Rudy Velthuis Aug 30 '15 at 17:11
  • @Johan: almost correct. I want to know how to simplify my code, i.e. avoid three negations of the full array. Your notion that I can stop negating as soon as the borrow bit (carry) is zero is a very good one, and paired with the known fact that `-A = not (A - 1)`, that gives me a really big boost. Thanks. – Rudy Velthuis Aug 30 '15 at 17:15
  • 1
    Fundamentally I think you are foolish not to learn from others. Denying yourself access to the leading extant implementations is, in my view, folly. – David Heffernan Aug 30 '15 at 17:22
  • It is foolish to write my own code, I guess. I could easily write a simple wrapper for GMP (or look for an existing one). I want to learn from others, and I have learned a lot from others, and the code of others, in the last 33 years. But I want to do this on my own and see how far I get. Until now, all of it works, but some of it seems rather slow. I already [solved one problem](http://stackoverflow.com/questions/32084204/problems-with-adc-sbb-and-inc-dec-in-tight-loops-on-some-cpus). – Rudy Velthuis Aug 30 '15 at 18:14
  • 1
    It's not foolish to write your own code. That's really how you cement learning. But if this were me I'd be reading the code from all major bigint libs, and reading the refs found within that code. – David Heffernan Aug 30 '15 at 18:54
  • FWIW, I had the code on my website, but [now put it on GitHub](https://github.com/rvelthuis/BigNumbers/blob/master/Source/Velthuis.BigIntegers.pas). – Rudy Velthuis Aug 07 '16 at 11:04

2 Answers2

6

Last time I checked negation worked like this:

-A = not(A) + 1; or
-A = not(A - 1);
that means that
-A and -B = not(A - 1) and not(B - 1)

if we add another NOT at the front than we can replace the and not with an or

not(-A and -B) = not(not(A - 1) and not(B - 1)) =
(A - 1) or (B - 1)

We still need to do an expensive not at the end, but because not is so close to - we can cheat and replace the expensive not with a cheap - like so: 

-(-A and -B) = (A-1) or (B-1) + 1;

And finally the outcome will be:

(-A and -B) = -((A-1) or (B-1) + 1);

This should be much faster than flipping all the bits.

This will be very cheap to implement because:

  1. Negation is a simple bit flip on your sign byte.
  2. +1/-1 will run out of carry/borrow bits very soon in the overwelming amount of cases (only 1/2^32 cases will carry/borrow to the next limb).

The same goes for or; not or is very close to and.

Johan
  • 74,508
  • 24
  • 191
  • 319
  • Thanks, that really helped me. Although, this still requires two subtractions, an addition and a negation, so that may not really simplify things. I'll check if I can take a few more shortcuts. – Rudy Velthuis Aug 30 '15 at 16:30
  • FWIW, in my implementation, a negation takes more or less the same time as a subtraction or an addition, all, AFAICT, in the order of O(n). – Rudy Velthuis Aug 30 '15 at 16:34
  • @RudyVelthuis, the -1 should take very little time, because you should run out of borrowing bits in the 1st-limb. except in 1/2^32 of cases (limb = $FFFFFFFF). So it will take O(1) time in 99.99999% of the cases. The negation is (nearly) free. – Johan Aug 30 '15 at 16:38
  • Note that negating the sign bit and doing a naive `and` is very different from doing a 2's complement negation and an `and`. So the implementation is really very cheap. – Johan Aug 30 '15 at 16:41
  • you could be right. I'll check how I can optimize -1 that way. – Rudy Velthuis Aug 30 '15 at 17:02
  • but note that I'll still have to `or` the full arrays, and that can't be eliminated. – Rudy Velthuis Aug 30 '15 at 18:03
  • Are you programming the lib in assembly? It seems a prime target for this. – Johan Aug 30 '15 at 18:10
  • I am programming the parts that do arithmetic (e.g. addition, subtraction, multiplication, division/remainder, bitwise operations, bit shifts, and a few utility functions) in Delphi's built-in 32-bit or 64-bit assembler for Windows, or "pure Pascal" for other platforms. The rest (e.g. parsing, ToString(), other simpler stuff, etc.) is done in plain Object Pascal. – Rudy Velthuis Aug 30 '15 at 21:14
  • This is exactly how GMP does it, FWIW – David Heffernan Aug 31 '15 at 08:52
  • And this is how Smalltalk VM does it too since the 1970s – aka.nice Sep 14 '15 at 21:00
1

My question is: are there similar laws I can use to avoid negating the magnitudes of "negative" BigIntegers?

Yes, and I did before what you want to do - see here, lines 105 - 115 (or better download the repository). Strange enough I also use the term 'Limb".

For example arrAndTwoCompl computes bitwise and of positive and negative, arrAndTwoCompl2 computes bitwise and of 2 negatives.

I've taken these 'laws' from GMP sources.

Don't reinvent big integers, just use them.

kludg
  • 27,213
  • 5
  • 67
  • 118