Last active
October 27, 2019 13:08
-
-
Save nvurgaft/0344b2aa4704219d07005e4d8b1d88a2 to your computer and use it in GitHub Desktop.
Example Big Number implementation in Java
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created by Nick on 1/28/2017. | |
*/ | |
public class BigNumber { | |
private Node head = null; | |
public BigNumber(BigNumber other) { | |
Node currentOther = other.getHead(); | |
Node current = head; | |
Node prev = current; | |
while (currentOther != null) { | |
Node newNode = new Node(); | |
newNode.setNext(null); | |
newNode.setData(currentOther.getData()); | |
if (head == null) { | |
head = newNode; | |
prev = newNode; | |
} else { | |
current = newNode; | |
prev.setNext(current); | |
prev = current; | |
} | |
currentOther = currentOther.getNext(); | |
} | |
} | |
public BigNumber(String number) { | |
boolean isNumber = true; | |
char[] chars = new StringBuffer(number).reverse().toString().toCharArray(); | |
for (char c : chars) { | |
if (!Character.isDigit(c)) { | |
isNumber = false; | |
break; | |
} | |
} | |
if (!isNumber) { | |
chars = new char[1]; | |
chars[0] = '0'; | |
} | |
Node current = head; | |
Node prev = current; | |
for (char c : chars) { | |
Node newNode = new Node(); | |
newNode.setNext(null); | |
newNode.setData(Character.digit(c, 10)); | |
if (head == null) { | |
head = newNode; | |
prev = newNode; | |
} else { | |
current = newNode; | |
prev.setNext(current); | |
prev = current; | |
} | |
} | |
} | |
public void append(BigNumber other) { | |
if (other == null) { | |
return; | |
} | |
Node current = other.getHead(); | |
while (current.getNext() != null) { | |
current = current.getNext(); | |
} | |
current.setNext(head); | |
head = other.getHead(); | |
} | |
public void add(BigNumber other) { | |
if (other == null) { | |
return; | |
} | |
Node currentOther = other.getHead(); | |
Node currentThis = this.getHead(); | |
int sum = 0; | |
int carry = 0; | |
int alen = other.toString().length(); | |
int blen = this.toString().length(); | |
int maxlen = (alen > blen ? alen : blen); | |
if (blen < alen) { | |
String padding = ""; | |
for (int i = 0; i < alen - blen; i++) { | |
padding += "0"; | |
} | |
BigNumber lpad = new BigNumber(padding); | |
lpad.append(this); | |
currentThis = lpad.getHead(); | |
} | |
for (int i = 0; i < maxlen; i++) { | |
int a = currentThis != null ? currentThis.getData() : 0; | |
int b = currentOther != null ? currentOther.getData() : 0; | |
int addition = a + b + carry; | |
sum = addition % 10; // 0 | |
currentThis.setData(sum); | |
carry = addition / 10; // 1 | |
if (currentOther.getNext() != null) { | |
currentOther = currentOther.getNext(); | |
} else if (i != maxlen - 1) { | |
currentOther.setData(0); | |
} | |
if (currentThis.getNext() != null) { | |
currentThis = currentThis.getNext(); | |
} else if (i != maxlen - 1) { | |
currentThis.setData(0); | |
} | |
} | |
if (carry > 0) { | |
if (currentThis.getNext() == null) { | |
Node newNode = new Node(); | |
newNode.setNext(null); | |
newNode.setData(carry); | |
currentThis.setNext(newNode); | |
} | |
} | |
} | |
public void add(Long other) { | |
if (other == null) { | |
return; | |
} | |
this.add(new BigNumber(other.toString() + "")); | |
} | |
public void mult(BigNumber other) { | |
if (other == null) { | |
return; | |
} | |
Node currentThis, currentOther; | |
if (other.toString().length() > this.toString().length()) { | |
currentThis = other.getHead(); | |
currentOther = this.getHead(); | |
} else { | |
currentThis = this.getHead(); | |
currentOther = other.getHead(); | |
} | |
BigNumber solution = new BigNumber("0"); | |
Node temp = currentThis; | |
int idx = 0; | |
while (currentOther != null) { | |
String pad = ""; | |
for (int j = 0; j < idx; j++) { | |
pad += "0"; | |
} | |
while (currentThis != null) { | |
long res = (currentThis.getData() * currentOther.getData()); | |
solution.add(new BigNumber(res + pad)); | |
currentThis = currentThis.getNext(); | |
pad += "0"; | |
} | |
currentOther = currentOther.getNext(); | |
currentThis = temp; | |
++idx; | |
} | |
this.head = solution.getHead(); | |
} | |
public Node getHead() { | |
return head; | |
} | |
@Override | |
public String toString() { | |
StringBuilder sb = new StringBuilder(); | |
Node current = head; | |
while (current != null) { | |
sb.insert(0, current.getData()); | |
current = current.getNext(); | |
} | |
return sb.toString(); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created by Nick on 1/28/2017. | |
*/ | |
public class Main { | |
public static void main(String[] args) { | |
BigNumber bigNumber1 = new BigNumber("123"); | |
System.out.println("big number: " + bigNumber1); | |
BigNumber bigNumber2 = new BigNumber("123234345456567678789890"); | |
System.out.println("big number: " + bigNumber2); | |
BigNumber bigNumber3 = new BigNumber("12323badbeef4345456567678789890"); | |
System.out.println("big number: " + bigNumber3); | |
BigNumber bigNumber4 = new BigNumber("-1"); | |
System.out.println("big number: " + bigNumber4); | |
BigNumber bigNumber5 = new BigNumber(bigNumber1); | |
System.out.println("big number: " + bigNumber5); | |
bigNumber5.append(new BigNumber("75")); | |
bigNumber5.append(new BigNumber("99")); | |
System.out.println("big number: " + bigNumber5); | |
BigNumber bigNumber10 = new BigNumber("999"); | |
bigNumber10.add( new BigNumber("999")); | |
bigNumber10.add(1234567890L); | |
System.out.println("addition: " + bigNumber10); | |
BigNumber bigNumber001 = new BigNumber("1234"); | |
BigNumber bigNumber002 = new BigNumber("4321"); | |
bigNumber001.mult(bigNumber002); | |
System.out.println("multiplication: " + bigNumber001); | |
} | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
/** | |
* Created by Nick on 1/28/2017. | |
*/ | |
public class Node { | |
int data; | |
Node next; | |
public int getData() { | |
return data; | |
} | |
public void setData(int data) { | |
this.data = data; | |
} | |
public Node getNext() { | |
return next; | |
} | |
public void setNext(Node next) { | |
this.next = next; | |
} | |
@Override | |
public String toString() { | |
return "Node{" + | |
"data=" + data + | |
'}'; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment
This is very simplistic implementation of a big number container represented as a linked list, similar in concept to Java's BigDecimal, the implementation isn't meant to be full or usable in a production code. The use of this code is as is, and I'm taking no responsibility for it.