# Integer lifting

Cairo programs use large numbers and sometimes it is useful to be able to perform checks on these numbers as part of some operation. One useful technique is to split the field element.

Firstly, to split a number is to divide it in two, as in with a visual divide between the left and right halves of the number.

## Decimal introduction

Consider the following:

Decimal number: `17,364,521`

- To split is to divide into two parts (
`1736`

and`4521`

) - High part
`1736`

, low part`4521`

. - So another way is to represent the number is:
`1736 * 10 ** 4 + 4521`

- You lift the integers from that representation get the high and low parts.
- The
`4`

in`10 ** 4`

comes from the idea of seeing how big the number is and dividing the power by two.`17,364,521`

has 8 digits, so it is of order`~10 ** 8`

(numbers less than`10 ** 9`

).`8 / 2`

is`4`

. So the high number has additional`10 ** 4`

zeros.- The system is decimal (base 10), so using
`10 ** (8 - 8/2)`

tells you how to split the number. `high * 10 ** 4 + low`

`high * base ** (order - order / 2) + low`

- See below for a base 2 (binary) example.

## Binary equivalent

If the same operation is performed in binary, the same process is followed.

Binary number: `10110011`

- Split into two parts (
`1011`

and`0011`

). - High part
`1011`

, low part`0011`

. - The order is
`8`

, the base is`2`

(binary number system) - High number will have additional
`4`

(`8/2`

) zeros. `high * 2 ** 4 + low`

.`1011 * 2 ** 4 + 0011`

.- High:
`1011`

, low:`0011`

.

## Larger example

Cairo uses numbers just less than 256-bit, rather than the 8-bit example above.

So for a number in Cairo, the integer lift would take the number, represent it as a 256 binary number, then divide it into two 128 (256/2) bits.

- Original number:
`100101010110101....101010100101001`

(256 digits long)

- Split number:
`100101010110101...`

(first 128 digits) and`...101010100101001`

(last 128 digits)

- With integer lifts:
`high * 2 ** 128 + low`

`high`

is a number that starts with`100101010110101...`

`low`

is a number that ends with`...101010100101001`

## Use case

The ability to divide a number in this way allows for more efficient operations, such as finding a neighbouring node in a binary tree.

In Cairo there are modules in the common library that take a field element, represent it as a binary number and then split the number as per the above examples.

For example, consider the 256-bit number:

`number = 0010000000...(more zeros)...0000001`

Divided into high and low parts:

- High:
`0010000000...000`

- Low:
`000...0000000001`

It is plain to see that `high`

is much greater than `low`

. This might be important to know
as part of some tree operation.

Another way to represent this might be two 128-bit components:
`00100.. * 2 ** 128 + ..00001`

or

`(2 ** 126) * 2 ** 128 + 1`

## Relationship to Cairo common library

So the operation:

`split_felt(number)`

that returns `high`

and `low`

.

Would return:

`high = 2 ** 126`

`low = 1`

The comparison operator:

`is_le_felt(a, b)`

Looks are two numbers `a`

, and `b`

and compares their respective `high`

lifts.
For example:

`a = 0010000000...(more zeros)...0000001`

(same as above)`a_high = 0010000000...000`

`b = 0001000000...(more zeros)...0000001`

`b_high = 0001000000...000`

It can be seen that `a`

is a larger number than `b`

.

The `is_le_felt(a, b)`

function checks if `a_high`

is less than or equal to `b_high`

.

It would return:

`0`

(false), because `a_high`

is not less than `b_high`

.

This method of checking the size of two numbers is more efficient (than a standard comparison) in some situations.

## Split felt implementation in Cairo

In the implementation of the function in the Cairo `math`

module, the number to be split
is parsed in the python hint as follows using bitwise shifts.

```
ids.high = ids.value >> 128
```

The high split is calculated by taking the 256-bit python integer, shifting it to the right by 128 places, thus removing the right-hand most 128 binary digits.

```
128 bits 128 bits = 256 bits total
|----------------------||----------------------|
1110101010101...010101011011011...11011011011011
^Highest bit ^^split point ^Lowest bit
(lost significant) (least significant)
value >> 128, the left half moves right, the right half is lost.
128 bits = 128 bits total
---> |----------------------|xxxxxxxx(lost)xxxxxxx
1110101010101...01010101
^Highest bit ^^split point
```

The low split is calculated by:

```
ids.low = ids.value & ((1 << 128) - 1)
```

Which saves the low 128 bits by creating a new number comprising only 128 1’s. Bitwise AND (&) is then used, which results in the loss of the high 128 bits.

```
128 bits 128 bits = 256 bits total
|----------------------||----------------------|
1110101010101...010101011011011...11011011011011
^Highest bit ^^split point ^Lowest bit
(lost significant) (least significant)
Bitwise AND on the 128 bit 1's.
000000000000000000000000111111111111111111111111
128 bits = 128 bits total
xxxxxxxxx(lost)xxxxxxxxx|----------------------|
1011011...11011011011011
^^split point
```