I'm trying to teach myself some programming and, working through the Project Euler problems, I've come across some instances where I've needed numbers that are larger than will fit into an int or long variable. I know that existing libraries already accomplish this, but I figured it would be fun/worthwhile/educational to build the tools to handle these myself.
Project Goals:
- Build a class to add or multiply numbers much larger than int or long.
- Prioritize cleanliness, extensibility, and ease of integration with other Project Euler solutions.
- Maximize algorithmic efficiency within these constraints.
Specific Questions:
Any feedback on style, structure, convention, etc.
Are there any profound improvements I could make to the algorithms.
Are there any features or techniques I should research to make this class more full-featured or comprehensive.
I appreciate any feedback, thank you.
public class MikesBigInt
{
private List<int> digits;
public int Length { get { return digits.Count; } }
public int this[int index] { get { return digits[index]; } }
public MikesBigInt()
{
digits = new List<int> { 0 };
}
public MikesBigInt(int n)
{
int l = n.ToString().Length;
digits = new List<int>();
for (int i = n.ToString().Length; i-- > 0;) {
digits.Add(n.ToString()[i] - 48);
}
}
public void Disp()
{
int l = digits.Count;
for (int i = digits.Count; i-- > 0;) {
Console.Write(digits[i]);
}
Console.WriteLine();
}
public int ToInt()
{
int res = 0;
for (int i = 0; i < digits.Count; i++) {
res += digits[i] * (int)Math.Pow(10, i);
}
return res;
}
public void Multiply(MikesBigInt n)
{
List<int> neoDigits = new List<int>();
int xL = digits.Count - 1;
int yL = n.Length - 1;
for (int i = 0; i < xL + yL + 2; i++) {
neoDigits.Add(0);
}
int carryTemp = 0;
for (int di = 0; di < neoDigits.Count; di++) {
int diVal = 0;
for (int x = Math.Max(0, di - yL); x <= Math.Min(di, xL); x++) {
diVal += (digits[x] * n[di - x]);
}
neoDigits[di] = (diVal + carryTemp) % 10;
carryTemp = ((diVal + carryTemp) - (diVal + carryTemp) % 10) / 10;
}
digits.Clear();
digits.AddRange(neoDigits);
Trim();
}
public void Multiply(int n)
{
int carryTemp = 0;
int l = digits.Count + n.ToString().Length;
for (int i = 0; i < n.ToString().Length + 8; i++) {
digits.Add(0);
}
for (int i = 0; i < l; i++) {
int d = digits[i] * n + carryTemp;
digits[i] = d % 10;
carryTemp = (d - d % 10) / 10;
}
for (int i = carryTemp.ToString().Length; i-- > 0;) {
digits.Add(carryTemp.ToString()[i] - 48);
}
Trim();
}
public void Add(MikesBigInt n)
{
int carryTemp = 0;
for (int di = 0; di < Math.Min(digits.Count, n.Length); di++) {
int diVal = digits[di] + n[di] + carryTemp;
digits[di] = diVal % 10;
carryTemp = (diVal - diVal % 10) / 10;
}
if (digits.Count > n.Length) {
for (int di = n.Length; di < digits.Count; di++) {
int diVal = digits[di] + carryTemp;
digits[di] = diVal % 10;
carryTemp = (diVal - diVal % 10) / 10;
}
}
else if (n.Length > digits.Count) {
for (int di = digits.Count; di < n.Length; di++) {
int diVal = n[di] + carryTemp;
digits.Add(diVal % 10);
carryTemp = (diVal - diVal % 10) / 10;
}
}
digits.Add(carryTemp);
Trim();
}
public void Add(int n)
{
Add(new MikesBigInt(n));
}
private void Trim()
{
if ((digits[digits.Count - 1] == 0) && (digits.Count > 1)) {
digits.RemoveAt(digits.Count - 1);
Trim();
}
}
}
List<int>
toList<byte>
to save a bit of memory for each digit, as you only need states 0-9, not (-2^31)-(2^31-1). (Side note: sorry for long comment) \$\endgroup\$