a more simple big adder in c#?

Question

I just had the task in school to write a big adder. Meaning a method that can put very large numbers together. We had 10 minutes and I did complete it on time. The teacher approved it.

I am not too satisfied with the result though, and I thought I perhaps were taking the wrong approach.

Here is my version:

using System; using System.Text; namespace kæmpe_adder { static class Program { static void Main() { var x = "1111"; var y = "111111111"; Console.WriteLine(BigAdder(x, y)); Console.ReadLine(); } public static StringBuilder BigAdder(string x, string y) { var a = new StringBuilder(x); var b = new StringBuilder(y); return BigAdder(a, b); } public static StringBuilder BigAdder(StringBuilder x, StringBuilder y) { int biggest; int carry = 0; int sum; var stringSum = new StringBuilder(); if (x.Length > y.Length) { y.FillString(x.Length - y.Length); biggest = x.Length; } else if (y.Length > x.Length) { x.FillString(y.Length - x.Length); biggest = y.Length; } else { biggest = y.Length; } for (int i = biggest - 1; i >= 0; i--) { sum = Convert.ToInt32(x[i].ToString()) + Convert.ToInt32(y[i].ToString()) + carry; carry = sum / 10; stringSum.Insert(0, sum % 10); } if (carry != 0) { stringSum.Insert(0, carry); } return stringSum; } public static void FillString(this StringBuilder str, int max) { for (int i = 0; i < max; i++) { str.Insert(0, "0"); } } } }

When I wrote it, I thought of how you do it with binaries.

Is there a shorter and/or perhaps simpler way to do this?

Note that this is NOT a school assignment. I did complete the assignment and now I am just curious for my own sake — CasperT
– CasperT, Commented Aug 27, 2009 at 11:16

Grzenio · Accepted Answer · 2009-08-27 11:23:21Z

From the algebraic point of view your code looks correct. From the design point of view, you would definitely prefer to encapsulate each of these big numbers in a class, so that you don't have to reference the string/string builders all the time. I am also not a big fan of this FillString approach, it seems more reasonable to add the digits while both numbers have non-zero values, and then just add the carry to the bigger number until you are done.

Not sure what was the question about binaries? The normal length numbers (32bit and 64bit) are added by the CPU as a single operation.

I am sorry - i just meant that I wanted to explain why I thought of this particular approach. My method is similar to how you add binary numbers

XXXXX · Accepted Answer · 2009-08-27 15:42:10Z

There are a number of open source implementations you could look to for inspiration.

http://www.codeproject.com/KB/cs/biginteger.aspx

http://biginteger.codeplex.com/

In general, I would recommend using an array of byte or long for best performance, but the conversion from a string to the array would be non-trivial.

Store the numbers in reverse order; this makes finding equivalent places trivial.

This makes it easier to add differently sized ~~strings~~ numbers:

int place = 0; int carry = 0; while ( place < shorter.Length ) { result.Append (AddDigits (longer[place], shorter[place], ref carry)); ++place; } while ( place < longer.Length ) { result.Append (AddDigits (longer[place], 0, ref carry)); ++place; } if ( carry != 0 ) result.Append (carry.ToString ());

Is this conversion fine? List<byte> xIntArray = x.Select(c => (byte) (c - '0')).ToList();
That's a little better than strings (1 byte instead of 2 per digit), but to really get the power of byte arrays, you want to use base 256 arithmetic, not just one decimal digit per byte. As I said, the conversion is non-trivial. For a class exercise, strings are good enough. Storing the numbers in reverse order is the real key.

Collectives™ on Stack Overflow

a more simple big adder in c#?

2 Answers 2

1 Comment

2 Comments

Hot Network Questions

Collectives™ on Stack Overflow

2 Answers 2

1 Comment

2 Comments

Related