# Solidity — Random Numbers

Published in

--

Hopefully, you know that it is impossible to generate a random number purely on-chain. You need to use services like chainlink, but let's be completely honest, pseudo-random is usually good enough for most needs.

However, sometimes you need multiple random numbers and things start to get expensive in terms of gas.

# Bit Shifting

Bit manipulation is really fun, or I have been diving way too deep into some very obscure articles. Either way, it's extremely useful and can be used to save you gas.

## What is bit shifting?

This subject and other byte manipulation techniques have been covered by people that are far smarter and more experienced than me:

## How do we use bit shifting with RNG?

Ok, imagine you need to generate 10 random numbers for attributes on your RPG NFT. You could create something like this:

The problem is you have to call it ten times.

There is a nice solution:

Just like that we only need to create a single randomHash and then use bit manipulation to create the 10 required random numbers.

Its worth noting that bit shifting doesn't mean you can shift forever, you will run out of bits. If you have a uint256 variable and you are shifting >> 16, you can only shift 16 times, cos 16 x 16 = 256.

I personally find it easier if there is some visual explanation of concepts and thought others might find a visual of bit shifting helpful.

And here is what happens if you shift beyond the available data. uint256 >> 16, 20 times:

# Random Number with Tracking

Sometimes you need to pick a random number from an existing list while tracking the numbers you have already picked.

In javascript this kind of task is trivial, but in solidity, you really have to put some thought into the methodology to save on gas.

## Random TokenId from Fixed Population

Imagine you have an NFT project with 10k tokens and you want to mint them out in random order. Most methods require a lot of looping and storing of data, which can get expensive and run the risk of gassing out.

## Magical Arrays

I have no idea what the proper name for this method is, so I just call it Magical Arrays :)

MAX_POPULATION: is the population count of the NFT we are creating.

ids: Is an empty array equal in length to MAX_POPULATION. If MAX_POPULATION is 5 then our array will look like this:

`[0,0,0,0,0]`

When pickId() is called a randomIndex is generated between 0 and the length of the array. This is important because we will be reducing the length of the array and ergo the range of possible randomIndex.

The next few lines of code are where the magic stuff starts to happen. I'll try to explain it as best I can.

## First Pass

Imagine our array [0, 0, 0, 0, 0], it is 5 elements long but every element is 0. Feels a little useless right? Cool thing is, this is extremely helpful.

Imagine our randomIndex value is 2. We check index 2 in the array and we can see the value is 0 so we set our return value of id to the index we just checked, 2.

`[0, 0, 0, 0, 0][2] = 0id = 2`

Now that we have an id value we need to edit our array to reflect what just happened and to ensure we don't lose any ids. Sounds like a lot to expect from an array.

If we don't edit the array a randomIndex value of 2 would result in the exact same return value and we don't want two NFTs with the tokenId of 2. To solve this problem we check to see if the last element in the array is equal to 0

`if(ids[ids.length-1] == 0)`

If it is, we replace the value at ids[randomIndex] with the index value of the last array element. That looks like this

`randomIndex = 2[0, 0, 4, 0, 0]`

Finally, we need to shrink the array by popping off the last element. This results in our array now looking like this.

`[0, 0, 4, 0]`

## Second Pass

When we pick our next id the randomIndex value again comes out as 2. Feels like this could be a problem, right — nope we got this covered.

First, we check if the value in the array at index 2 is equal to 0. We can see that it is equal to 4

`[0, 0, 4, 0]`

In the first pass, our index value was equal to 0 and so we returned the randomIndex value of 2. This time we have a value of 4, so we return the 4.

Just like the first pass, we need to edit the array to reflect what just happened. Resulting in our array now looking like this:

`[0, 0, 3]`

## Third Pass

Wouldnt you know it, randomIndex rolled another 2.

This time the value at index 2 is a 3, so we will return 3 and edit the array to reflect the event.

This time things are a little different, the last value in the array is not equal to 0 and so we have to do things a little differently and the resulting array ends up being

`[0, 0]`

## Magic Array

I know this can be a little tricky to get your head around and the first time I played with it I was mapping arrays out on paper just to make sure I fully understood the concept.

## Christmas Teaser

The magic array code sample above can be optimized, can you see how?

# Where to find me

I can normally be found in the Cool Cats discord channel
https://discord.gg/WhBAAHnSz4

# Last Word

I feel silly saying this, but I have had so many messages I feel it might save you and me some time.

I work full time on Cool Cats I am swamped with work, so sadly I have to decline every job offer.

But I am always willing to help out by sharing resources and advice where I can.