Printable View
Hello!
I need to convert a binary expression liketo a decimal string likeCode:bool[] {1,1,0,1,0,1......1,0,0,1,0,1,1,0,1}
the clue is, that the binary number can contain a million binary digits and the resulting decimal string could be very long. it's a little like using Blobs, only i have to do it myself.Code:"1890125081"
does anyone know how to do this? google couldn't help me at this one... it's damaging my brain right now...
thanks.
Give this a try, it's based on some javascript online convertor i found here http://compnetworking.about.com/od/b...nvertbases.htm - there's also decimal string back to binary if you want that.
Code:using System;
namespace ConsoleApplication8
{
class Program
{
static int Main()
{
int[] bin = new int[] { 1, 0, 1, 0, 0, 1, 1, 1 }; // should convert to 167
Console.WriteLine(Binary2DecimalString(bin));
Console.Read();
return 1;
}
static String Binary2DecimalString(int[] bin)
{
double d = 0;
for (int i = 0; i < bin.Length; i++)
d += bin[i] * Math.Pow(2, bin.Length - i - 1);
return d.ToString();
}
}
}
well, thats the point i described above. you are using double, but my numbers are not 64-bit sized but more like 2^2^32 = 4 GB numbers
they will never fit into a double...
In general, binary to decimal conversion on arbitrarily large numbers is highly challenging; you're running up against the physical limits of how much memory you can allocate.
For that matter, you can't even CREATE a boolean array with 2^32 entries; 2^31 - 1 is the maximum possible index value since all arrays are indexed with 32 bit signed integers. And on a 32 bit system the runtime wouldn't even be able to allocate that much address space.
If you really wanted to do it, you'd likely need to use files on disk to store your input and 'variables' -- you'd run out of memory space if you tried to use conventional variables. You'd really only need one key function: Read a decimal 'variable' file, and double the number contained within, optionally incrementing it by one during the doubling.
The easiest way would be to store the decimal numbers little-endian -- so the number 43,579 would be stored as the bytes [9 7 5 3 4] in a file. Then you'd just have a function that would go byte-by-byte and double the number, carrying any tens digit; for the first digit there'd also be the option to add one. So in this case, say you doubled and did add 1:
* Compute 9 * 2 + 1 (this is the optional 1) = 19, write 9 to the output stream, save the 1 as a carry to the next digit
* Compute 7 * 2 + 1 (the carry) = 15, write the 5, carry the 1
and so on until you've written [ 9 5 1 7 8 ]
You can actually, assuming you open the output file for both read/write, modify the file in-place so you don't actually need any more than a few bytes of temporary storage (in RAM) to hold digits as they are being processed. Likewise, you could reverse the number at the end of the operation in-place as well, if you wanted to have a far more human-readable big-endian number.
How would this function help you convert binary to decimal? You use this algorithm to do your conversions:
1. Start reading the bits starting with the most significant '1' bit. Set the initial output value to be 1, the value of this bit. (of course, if there are no '1' bits, your answer is zero and you're done).
2. While there are more bits in the number (remember you're reading the binary starting at MSB and moving towards LSB), double the previous output and add the next bit (either 0 or 1 -- this is why the functionality to add 1 is there) -- save this as the new output.
3. When there are no more bits, your output is now the (little endian) representation of that binary number. You can now reverse the digits if you want it big-endian.
Oh, and one tip that would make the whole process more efficient: you could write your "doubling and increment" code to read / write an entire cluster at a time (typically 4 KB on modern machines, but somewhat challenging to find programmatically) .
ok. here is the conversion algorithm i've found out:it converts my LargeInt to a decimal string. the only problem is, that i would need division and modulu implementation in my LargeInt class.Code:static string DecimalToBase(LargeInt number)
{
string ret = "";
for (; number > 0; number /= 10)
{
int rem = number % 10;
ret = rem + ret;
}
return ret;
}
i simply don't know how to divide two numbers.
i'm currently playing arroun with it, i think i'll be getting it solved!
Doubles can be infinite size. See double.IsInfinity(). Decimals are finite.Quote:
you are using double, but my numbers are not 64-bit sized but more like 2^2^32 = 4 GB numbers they will never fit into a double
ok. i've got the bin-dec conversion working:but because of those many divisions it is damn slow!!! does anybody know how to speed this up?Code:Blob num = Clone();
while (num > 0)
{
num /= 10;
Blob rem = ModuloFlag;
int rem2 = 0;
if (rem.Raw[Size - 1]) rem2++;
if (rem.Raw[Size - 2]) rem2 += 2;
if (rem.Raw[Size - 3]) rem2 += 4;
if (rem.Raw[Size - 4]) rem2 += 8;
ret = rem2 + ret;
}
if (ret.Length == 0) ret = "0";
-Don't have all the code, maybe all those ifs can be simplifiedQuote:
Originally Posted by Devils Child
-Since Blob is initialized once, the initialization should be done outside the while-loop, so it doesn't happen all the time.
-rem2 is not really needed. You can simply directly increase ret.
prog-bman: Read the post first, then answer.
c_nuta: here is my blob code:
it is a blob class. you can do any math operations on any numbers. the ToString() method converts it to a decimal, i've extracted the ret/=10 code into some binary ops. but it's still slow...
Code:using System;
using System.Windows.Forms;
namespace LargeNumbers
{
static public class Program
{
static public void Main()
{
DateTime time = DateTime.Now;
Blob num = new Blob(3).Pow(300);
Console.WriteLine(num.ToString());
DateTime time2 = DateTime.Now;
Console.WriteLine();
Console.WriteLine("ms: " + (time2 - time).TotalMilliseconds);
Console.ReadKey();
}
}
public class Blob
{
public const int Size = 512;
static private readonly ulong[] Potency =
{
0x1,0x2,0x4,0x8,0x10,0x20,0x40,0x80,0x100,0x200,0x400,0x800,0x1000,0x2000,0x4000,0x8000,0x10000,0x20000,0x40000,0x80000,0x100000,0x200000,0x400000,0x800000,
0x1000000,0x2000000,0x4000000,0x8000000,0x10000000,0x20000000,0x40000000,0x80000000,0x100000000,0x200000000,0x400000000,0x800000000,0x1000000000,
0x2000000000,0x4000000000,0x8000000000,0x10000000000,0x20000000000,0x40000000000,0x80000000000,0x100000000000,0x200000000000,0x400000000000,0x800000000000,
0x1000000000000,0x2000000000000,0x4000000000000,0x8000000000000,0x10000000000000,0x20000000000000,0x40000000000000,0x80000000000000,0x100000000000000,
0x200000000000000,0x400000000000000,0x800000000000000,0x1000000000000000,0x2000000000000000,0x4000000000000000,0x8000000000000000,
};
static public Blob MinValue
{
get
{
Blob ret = new Blob();
ret.Raw[0] = true;
ret.Raw[Size - 1] = true;
return ret;
}
}
static public Blob MaxValue
{
get
{
Blob ret = new Blob();
for (int i = 1; i < Size; i++)
{
ret.Raw[i] = true;
}
return ret;
}
}
private bool[] Raw;
public bool this[int index]
{
get
{
if (index < 0 || index >= Size) throw new IndexOutOfRangeException();
return Raw[index];
}
set
{
if (index < 0 || index >= Size) throw new IndexOutOfRangeException();
Raw[index] = value;
}
}
public Blob()
{
Raw = new bool[Size];
}
public Blob(long number)
{
Raw = new bool[Size];
if (number >= 0)
{
for (int i = 0; i < 64; i++)
{
Raw[Size - 64 + i] = (Convert.ToUInt64(number) & Potency[63 - i]) > 0;
}
}
else
{
number = ~number;
for (int i = 0; i < 64; i++)
{
Raw[Size - 64 + i] = (Convert.ToUInt64(number) & Potency[63 - i]) > 0;
}
Raw = (~this).Raw;
}
}
private Blob(bool[] raw)
{
Raw = raw;
}
static public Blob Parse(string decimalNumber)
{
return Parse(decimalNumber, NumberFormat.Decimal);
}
static public Blob Parse(string number, NumberFormat format)
{
Blob ret = new Blob();
switch (format)
{
case NumberFormat.Binary:
for (int i = number.Length - 1; i >= 0; i--)
{
switch (number[number.Length - i - 1])
{
case '0':
break;
case '1':
ret.Raw[Size - i - 1] = true;
break;
default:
throw new FormatException();
}
}
break;
case NumberFormat.Decimal:
bool neg = number.StartsWith("-");
if (neg) number = number.Substring(1);
Blob p = 1;
Blob ten = 10;
for (int i = number.Length - 1; i >= 0; i--, p *= ten)
{
if (number[i] < 48 || number[i] > 57) throw new FormatException();
ret += new Blob(Convert.ToInt64(number[i] - 48)) * p;
}
if (neg) ret = -ret;
break;
case NumberFormat.Hexadecimal:
number = number.ToLower();
for (int i = number.Length - 1; i >= 0; i--)
{
char cur = number[number.Length - i - 1];
int cur2 = 0;
if (cur > 47 && cur < 58)
{
cur2 = cur - 48;
}
else if (cur > 96 && cur < 103)
{
cur2 = cur - 87;
}
else
{
throw new FormatException();
}
for (int a = 0; a < 4; a++)
{
ret.Raw[Size - 4 - i * 4 + a] = (Convert.ToUInt32(cur2) & Potency[3 - a]) > 0;
}
}
break;
}
return ret;
}
public override string ToString()
{
return ToString(NumberFormat.Decimal);
}
public string ToString(NumberFormat format)
{
string ret = "";
switch (format)
{
case NumberFormat.Binary:
foreach (bool bo in Raw)
{
ret += bo ? 1 : 0;
}
break;
case NumberFormat.Decimal:
Blob num = Clone();
bool neg = Raw[0];
if (neg) num = -num;
bool m0, m1, m2, m3, m4;
while (num > 0)
{
m0 = false; m1 = false; m2 = false; m3 = false; m4 = false;
for (int i = 0; i < Size; i++)
{
m0 = m1; m1 = m2; m2 = m3;
m3 = m4; m4 = num.Raw[0];
for (int a = 0; a < Size - 1; a++) num.Raw[a] = num.Raw[a + 1];
num.Raw[Size - 1] = false;
bool bigger = true;
if (m0) bigger = true;
else if (!m1) bigger = false;
else if (m2) bigger = true;
else if (!m3) bigger = false;
if (bigger)
{
bool car = m3;
m3 = !m3;
if (m2)
{
m2 = car;
car = true;
}
else
{
m2 = !car;
}
m1 ^= car;
bool b = true;
for (int a = Size - 1; a >= 0 && b; a--)
{
b = num.Raw[a];
num.Raw[a] = true;
}
}
}
int rem2 = Convert.ToInt32(m4);
if (m3) rem2 += 2;
if (m2) rem2 += 4;
if (m1) rem2 += 8;
ret = rem2 + ret;
}
if (ret.Length == 0) ret = "0";
if (neg) ret = "-" + ret;
break;
case NumberFormat.Hexadecimal:
for (int i = 0; i < Size / 8; i++)
{
int by = 0;
for (int a = 0; a < 8; a++)
{
if (Raw[i * 8 + a]) by += 1 << 7 - a;
}
ret += by.ToString("x2");
}
break;
}
return ret;
}
public override int GetHashCode()
{
return 0;
}
public override bool Equals(object obj)
{
return false;
}
public Blob Clone()
{
return new Blob((bool[])Raw.Clone());
}
static public Blob operator +(Blob num1, Blob num2)
{
Blob ret = num1.Clone();
bool[] raw1 = ret.Raw, raw2 = num2.Raw;
bool car = false;
for (int i = Size - 1; i >= 0; i--)
{
if (raw1[i] ^ raw2[i])
{
raw1[i] = !car;
}
else if (raw1[i] && raw2[i])
{
raw1[i] = car;
car = true;
}
else
{
raw1[i] = car;
car = false;
}
}
return ret;
}
static public Blob operator ++(Blob num)
{
bool b = true;
for (int i = Size - 1; i >= 0 && b; i--)
{
b = num.Raw[i];
num.Raw[i] = !num.Raw[i];
}
return num;
}
static public Blob operator -(Blob num1, Blob num2)
{
return num1 + ~num2 + 1;
}
static public Blob operator -(Blob num)
{
return ~num + 1;
}
static public Blob operator --(Blob num)
{
num -= 1;
return num;
}
static public Blob operator *(Blob num1, Blob num2)
{
Blob res = new Blob();
for (int i = 0; i < Size; i++)
{
if (num2.Raw[i]) res += num1 << Size - i - 1;
}
return res;
}
static public Blob operator /(Blob dividend, Blob divisor)
{
if (divisor == 0) throw new DivideByZeroException();
Blob num1 = dividend.Clone(), num2 = divisor.Clone();
bool n1s = num1.Raw[0], n2s = num2.Raw[0];
if (n1s) num1 = -num1;
if (n2s) num2 = -num2;
Blob mod = new Blob();
for (int i = 0; i < Size; i++)
{
mod <<= 1;
if (num1.Raw[0]) mod.Raw[Size - 1] = true;
num1 <<= 1;
if (mod >= num2)
{
mod -= num2;
num1++;
}
}
return n1s ^ n2s ? -num1 : num1;
}
static public Blob operator %(Blob dividend, Blob divisor)
{
if (divisor == 0) throw new DivideByZeroException();
Blob num1 = dividend.Clone(), num2 = divisor.Clone();
bool n1s = num1.Raw[0], n2s = num2.Raw[0];
if (n1s) num1 = -num1;
if (n2s) num2 = -num2;
Blob mod = new Blob();
for (int i = 0; i < Size; i++)
{
mod <<= 1;
if (num1.Raw[0]) mod.Raw[Size - 1] = true;
num1 <<= 1;
if (mod >= num2)
{
mod -= num2;
num1++;
}
}
return mod;
}
static public Blob operator <<(Blob num1, int num2)
{
if (num2 < 0) return num1 >> -num2;
num2 %= Size;
Blob ret = new Blob();
bool[] raw = ret.Raw;
for (int i = 0; i < Size; i++)
{
int p = i + num2;
if (p < 0)
{
raw[i] = num1.Raw[0];
}
else if (p >= Size)
{
raw[i] = false;
}
else
{
raw[i] = num1.Raw[p];
}
}
return ret;
}
static public Blob operator >>(Blob num1, int num2)
{
if (num2 < 0) return num1 << -num2;
num2 %= Size;
Blob ret = new Blob();
bool[] raw = ret.Raw;
for (int i = 0; i < Size; i++)
{
int p = i - num2;
if (p < 0)
{
raw[i] = num1.Raw[0];
}
else if (p >= Size)
{
raw[i] = false;
}
else
{
raw[i] = num1.Raw[p];
}
}
return ret;
}
static public Blob operator ~(Blob num)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = !num.Raw[i];
}
return ret;
}
static public Blob operator |(Blob num1, Blob num2)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = num1.Raw[i] | num2.Raw[i];
}
return ret;
}
static public Blob operator &(Blob num1, Blob num2)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = num1.Raw[i] & num2.Raw[i];
}
return ret;
}
static public Blob operator ^(Blob num1, Blob num2)
{
Blob ret = new Blob();
for (int i = 0; i < Size; i++)
{
ret.Raw[i] = num1.Raw[i] ^ num2.Raw[i];
}
return ret;
}
static public bool operator ==(Blob num1, Blob num2)
{
for (int i = 0; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return false;
}
return true;
}
static public bool operator !=(Blob num1, Blob num2)
{
for (int i = 0; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return true;
}
return false;
}
static public bool operator >(Blob num1, Blob num2)
{
if (num1.Raw[0] && !num2.Raw[0])
{
return false;
}
else if (!num1.Raw[0] && num2.Raw[0])
{
return true;
}
else
{
for (int i = 1; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return num1.Raw[i] && !num2.Raw[i];
}
return false;
}
}
static public bool operator <(Blob num1, Blob num2)
{
if (num1.Raw[0] && !num2.Raw[0])
{
return true;
}
else if (!num1.Raw[0] && num2.Raw[0])
{
return false;
}
else
{
for (int i = 1; i < Size; i++)
{
if (num1.Raw[i] != num2.Raw[i]) return !num1.Raw[i] && num2.Raw[i];
}
return false;
}
}
static public bool operator >=(Blob num1, Blob num2)
{
return num1 > num2 || num1 == num2;
}
static public bool operator <=(Blob num1, Blob num2)
{
return num1 < num2 || num1 == num2;
}
static public implicit operator Blob(long num)
{
return new Blob(num);
}
public Blob Pow(uint pow)
{
Blob ret = 1;
Blob p = Clone();
int to = 0;
for (int i = 32; i >= 0; i--)
{
if ((pow & Potency[i]) > 0)
{
to = i + 1;
break;
}
}
for (int i = 0; i < to; i++)
{
if ((pow & Potency[i]) > 0)
{
ret *= p;
}
p *= p;
}
return ret;
}
}
public enum NumberFormat
{
Binary, Decimal, Hexadecimal
}
}