In Javascript, if the number is equal or less than 9007199254740991 (Number.MAX_SAFE_INTEGER) then we can simply use MODULO ('%') operation, such as
function getLastDigitValue(number) { return (number % 10); } getLastDigitValue(7); // return 7 getLastDigitValue(85); // return 5 getLastDigitValue(87129); // return 9 getLastDigitValue(189712); // return 2
It is easy for a small number when it can be stored inside native JS 'Number' data type, but what if the number is a very large value and represented using long binary, such as 1024 bits? in this case, we need to use Large Integer library (BigInteger class or others).
This article is just a simple reminder, (especially for me ;-P), without using any large integer library, we can get the last digit value of any number using simple bit operation.
A number is represented as a group of bits in machine, each bit has its own value, the following table shows each bit position and its value.
bit | binary | value | last digit value |
---|---|---|---|
1st | 1 | 1 | 1 |
2nd | 01 | 2 | 2 |
3rd | 001 | 4 | 4 |
4th | 0001 | 8 | 8 |
5th | 00001 | 16 | 6 |
6th | 000001 | 32 | 2 |
7th | 0000001 | 64 | 4 |
8th | 00000001 | 128 | 8 |
9th | 000000001 | 256 | 6 |
10th | 0000000001 | 512 | 2 |
11th | 00000000001 | 1024 | 4 |
12th | 000000000001 | 2048 | 8 |
13th | 0000000000001 | 4096 | 6 |
14th | 00000000000001 | 8192 | 2 |
etc. |
From the table above, we can see the first bit is either ZERO ('0') or ONE ('1'), this first bit is very important to know if the number is an odd number or an even number, then starting from 2nd bit the last digit value is a 2 then the next bit ends with a 4 then the next bit ends with an 8 then the next bit ends with a 6 then 2 then 4 then 8 then 6 then repeat to 2 again and so on, we can see this has a repetitive pattern and it is infinite.
Since we are only interested to see what is the last digit of a large number which consisted of long bits (more than 64 bits), then we need to keep calculate the last digit values only, the table below showing the logic and only using a small number.
number | 1 [1] |
2 [2] |
4 [4] |
8 [8] |
16 [6] |
32 [2] |
64 [4] |
128 [8] |
256 [6] |
512 [2] |
1024 [4] |
2048 [8] |
4096 [6] |
8192 [2] |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
265 | 1 [1] |
0 | 0 | 1 [8] |
0 | 0 | 0 | 0 | 1 [6] |
|||||
265 = "100100001" (represented in 9 bits),
accumulation of all last digits: 1+8+6 = 15 = 5 (the last digit) |
||||||||||||||
16003 | 1 [1] |
1 [2] |
0 | 0 | 0 | 0 | 0 | 1 [8] |
0 | 1 [2] |
1 [4] |
1 [8] |
1 [6] |
1 [2] |
16003 = "11000001011111" (represented in 14 bits),
accumulation of all last digits: 1+2+8+2+4+8+6+2 = 33 = 3 (the last digit) |
||||||||||||||
16318 | 0 | 1 [2] |
1 [4] |
1 [8] |
1 [6] |
1 [2] |
0 | 1 [8] |
1 [6] |
1 [2] |
1 [4] |
1 [8] |
1 [6] |
1 [2] |
16318 = "01111101111111 (represented in 14 bits),
accumulation of all last digits: 2+4+8+6+2+8+6+2+4+8+6+2 = 58 = 8 (the last digit) |
We could use a larger number with longer bit and the logic is similar to the above calculation. Using Javascript to get bits string of a number is as simple as:
function getBitsString(number) { return number.toString(2).split('').reverse().join(''); } getBitsString(123456789); // '101010001011001111011010111' getBitsString(Number.MAX_SAFE_INTEGER) // '11111111111111111111111111111111111111111111111111111'
The code to calculate the last digit value is easy too, such as:
function getLastDigitValue(longBitsString) { let bitsLength = longBitsString.length; if(bitsLength < 1) { return 0; } // get the first bit value let lastDigitValue = (longBitsString[0] == '0' ? 0 : 1); // define constant array for accumulation const BitPositionLastDigitValue = [2, 4, 8, 6]; // do the second bit position and to the last for(let i = 1; i < bitsLength; i++) { lastDigitValue = (lastDigitValue + (longBitsString[i] == '0' ? 0 : BitPositionLastDigitValue[(i - 1) % 4])) % 10; } return lastDigitValue }
Simple demonstration, please type in a long text with either '0' or '1' to get the last digit value:
* NOTE: if character is not '0' then it will be assumed as '1'
Total bit is
Last digit value is
Using BigInt to parse the value:
My original plan to use this logic is related to prime number checking, to know what is the last digit value of a large number (ie: more than one thousand digits) can help to cut the operation time for:
- When we use a function to 'generate a random odd large number' (could be thousands or millions of bits long) for prime number checking, usually after we have created an odd large number then the next thing to do is to check if that number ends with a 5 or not, if it ends with a 5 then it is not a prime number because only number 5 (single digit) is a prime number ends with 5, knowing this info will cut the prime checking time because we can skip the number.
- Generate random odd large number is taking a small CPU resource, so we can avoid it by checking if the first (or previous) generated a random number is not a prime number then we can get the next value without starting the process to generate another random odd large number again, such as if the previous number ends with a '1' then we can add 2 to make it ends with a '3' for the next possible number to check, also if the previous value ends with a '3' then we can add 4 (to skip '5') to make it ends with a '7' for the next possible number to check, and so on.
This is just one way to calculate the last digit value, maybe there is another way (and hopefully more effective) also without using integer class. If anyone knows another way then please share with me, thanks.
What is the current largest known prime number ? see Largest known prime number
Extra notes
- For an even composite number, the factor list will at least have a '2'
- For an odd composite number that ends with '5' (ie: 15, 105, 9999215, etc.), the factor list will at least have a '5'