Comment by X4 | Hacker News Reader

Comment by X4 | Hacker News Reader

Hi,

I don't understand the problem with a) rounding floats to integer and I don't understand b) why you would ever have to overflow an integers.

a) Wouldn't it solve the problem to write an algorithm that can use mathematical axioms like +,-,/,* virtually using strings? I mean you want it to calculate 99999999999999999999999999999999999999999999999999999 + 9999999999999999999999999999, why not teach it how we do this instead of having to use bit-hacking tricks? Maybe my example isn't good, but I mean writing an algorithm that reads 999 for example and 1000 knows that it now has to put a 1 infront of 999. You see, that's what I mean by manually.

b) And can you please explain "why" it isn't enough to use ie. a linked list of 8bit virtual address spaces and allocate using virtual address spaces everything that fits into RAM and everything that goes beyond the addressable space onto swap?

Why would you have to worry about flipping bits in an overflowed integer/float, when you could use that mechanism. Don't you just recursively run through the virtual address map until you're able modify the allocated data in that memory segments again? I don't see a problem with this implementation except for performance maybe.

When the algirhtms knows about the 32bit limit for example (constant), you can tell it to not allocate real memory with that size, but allocate virtual memory with that size dependant on the input data size. Yes I know that the CPU has built-in mechanism for the mathematical axioms, but doing it manually would solve the problem, from my limited perspective.

Sorry if I'm blind for seeing the problem, I'm not ignorant, just really curious in how this can be solved once and forever.

"I'm not ignorant" - of math operations in a computer, I'm afraid I have to contradict you.

Using Strings to represent numbers is fine if you have all day. There are numerous libraries that perform Biginteger math - doing it as we're taught in grade school (in essence).

Number formats can be quite complex, for example, you might also want the byte layout to be lexically sortable (sort as 'characters' and end up with a numerically sorted list)

Refer to Knuth for how all this works.

Just to make sure this is clear: bigint libraries do not use strings.

A well coded big int library will use an array of ints. When an overflow is detected (the processor has a flag for this) you expand the array appropriately.

Some libraries don't wait to detect the overflow, in fact they compute how many bytes are required for a certain operation (easy to do with bitmasks) and allocate the appropriate size ahead of time (this is useful if you overflow often)

The thing is, computers have dedicated hardware to deal with binary numbers. Compared to using strings (or other representations), they allow you to do math 100-1000 times faster (probably even more). When you actually start programming, you start getting used to these limits, and realise that for 90% of programs they don't matter. If your program ever did reach those limits, there are libraries you can switch to to get around it, which use alternate representations. But these can get quite slow, and hard to use.

So in summary, the best description is "performance".

a) That solution is sometimes implanted. The problem is: its slow, very, very, slow. It is not nearly as fast as regular integer arithmetic. (Also, +, -, /, and * aren't called axioms.) Also, how do you handle things such as powers and exponentiation (especially non-integer arguments)?

b) Search up for "BigInt libraries". The problem is the same with the others, its slow. You still have to allocate memory and the operations aren't as fast. However, BigInt libraries are widely used when necessary.

@omra, why downvote a question? It wasn't a proposed solution to the problem, it was a question on if there is a solution similar to that and otherwise why this would be wrong. I have added that I believe that this would be slow, if you read it carefully.

Btw. "axiom" was probably an unlucky translation of "Körperaxiom". See: http://de.wikipedia.org/wiki/K%C3%B6rper_%28Algebra%29 The english wikipedia says:

"The most common way to formalize this is by defining a field as a set together with two operations, usually called addition and multiplication, and denoted by + and ·, respectively, such that the following axioms hold; subtraction and division are defined implicitly in terms of the inverse operations of addition and multiplication"

omra likely did not downvote your question.

Are (well implemented) BigInt libraries actually significantly slower in the cases where the underlying primitive is large enough.

For example, say it is implemented as a singly-linked-list of ints. The input to the addition function is a pointer to the heads of 2 BigInts. To do the addition:

Dereference the 2 pointers. Perform the primitive addition. Check the overflow bit Check the 2 'next' pointers. if(hasNext OR overflow) ...

Assuming normal ints would suffice, (hasNext OR overflow) would be false, so you are done. Also, if it is always false, then branch prediction would guess correctly here.

Reply on news.ycombinator.com