Skip to content

Instantly share code, notes, and snippets.

@nvurgaft
Last active October 27, 2019 13:08
Show Gist options
  • Save nvurgaft/0344b2aa4704219d07005e4d8b1d88a2 to your computer and use it in GitHub Desktop.
Save nvurgaft/0344b2aa4704219d07005e4d8b1d88a2 to your computer and use it in GitHub Desktop.
Example Big Number implementation in Java
/**
* 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();
}
}
/**
* 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);
}
}
/**
* 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 +
'}';
}
}
@nvurgaft
Copy link
Author

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.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment