data structures - BigInt and indirection: is it feasible to implement BigInt with pointer-arithmetic on the pointer, for small values? -

i assume implementation in language allows treat pointers integers, including doing standard arithmetic on them. if unrealistic due hardware constraints, please let me know. if programming languages don't have such powerful pointer arithmetic, feasible in practice, still want know if approach implementing bigint feasible.

i don't have experience low-level - in, programming pointers - programming, many of assumptions in following might wrong.

---

question: far know, implementing bigint - arbitrary precision/size integer - might done dynamic array of integers, grows needed. data structure might represented pointer array of integers. but, assuming pointer integer ones in array, , 1 can pointer arithmetic on pointer, feasible represent value of bigint using pointer? 1 can avoid indirection small values of integers.

since pointer either real pointer memory address array of integers, have have way of knowing should treat pointer or integer value. since role through life cycle of bigint. suppose setting significant bit 1 if pointer pointer, 0 otherwise. far being integer concerned, seems simple enough: check if set 1 before doing it. if not, whatever arithmetic on in particular , see if has overflown, , appropriate thing if did.

but has problem: pointer use full range point memory addresses? if so, there doesn't seem way of using bit-pattern distinguish integers pointers: every bit-pattern potential memory address. seems reasonable pointers represented signed integers, though mind might represented unsigned integers if makes implementation simpler.

so, if pointers signed; don't seem able use pointers integers, purpose. if so, feasible (that is: efficient compared alternatives) represent bigint struct (or record, if want) 2 members; pointer array , integer used when value of bigint small? if pointer array null, integer used. if not, use pointer array , ignore int in struct. makes more "bloated" data structure, might when comes avoiding indirection sometimes, assuming don't need pointer struct , can pass around value.

another question: done in practice?

on 32-bit machines, lower 2 bits on pointers 0 because addresses 32-bit aligned. similarly, on 64-bit machines, lower 3 bits 0.

you can use fact use least-significant bit of pointer tag whether it's number or not. 1 simple option set lsb 1 if it's number , 0 if it's pointer. when performing arithmetic computations, first check lsb see whether have pointer or integer. if it's 1, arithmetically right-shift number on 1 bit real integer value, use value in computation. if it's 0, follow pointer representation.

you conceivably use fact have 2 or 3 bits of space encode more possible representations. example, have number either integer, pointer fixed-sized buffer, or pointer variable-sized buffer, using free pointer bits encode case happen in.

hope helps!