Я очень сильно хочу сделать свою библиотеку для работы с большими числами. Я начал ее делать. И понял что не знаю как ее сделать.
public struct BigInt
{
private byte[] Value { get; set; }
public BigInt(string value)
{
if (value.Length != 0)
Value = new byte[value.Length];
else
{
Value = null;
return;
}
for (int i = value.Length - 1; i >= 0; i--)
Value[i] = (byte)value[i];
}
public BigInt(byte[] value) { this.Value = value; }
public override string ToString() => Encoding.Default.GetString(Value);
public static implicit operator BigInt(string num) => new BigInt(num);
public static implicit operator string(BigInt num) => Encoding.Default.GetString(num.Value);
public static string operator +(BigInt c1, BigInt c2) => Addition(c1.Value, c2.Value);
public static string operator +(BigInt c1, string c2) => Addition(c1.Value, Encoding.Default.GetBytes(c2));
public static string operator *(BigInt c1, BigInt c2) => Multiplication(c1.Value, c2.Value);
public static string operator *(BigInt c1, string c2) => Multiplication(c1.Value, Encoding.Default.GetBytes(c2));
public static string Addition(byte[] x, byte[] y)
{
List<byte> result = new List<byte>();
int c = 0, d = 0;
List<byte> z = new List<byte>();
if(x.Length > y.Length)
{
z.InsertRange(0, Encoding.Default.GetBytes(new String('0', x.Length - y.Length).ToCharArray()));
z.AddRange(y);
y = z.ToArray();
}
else
{
z.InsertRange(0, Encoding.Default.GetBytes(new String('0', y.Length - x.Length).ToCharArray()));
z.AddRange(x);
x = z.ToArray();
}
for(int i = x.Length-1; i>=0; i--)
{
byte a = x[i];
byte b = y[i];
c = (d + (a % 48) + (b % 48)) % 10;
result.Add((byte)c);
d = (d + a % 48 + b % 48) / 10;
}
if (d != 0)
result.Add((byte)d);
result.Reverse();
return string.Join("", result);
}
public static string Multiplication(byte[] x, byte[] y)
{
List<byte>[] result = new List<byte>[y.Length];
for (int i = 0; i < y.Length; i++)
{
int c = 0;
int d = 0;
List<byte> array = new List<byte>();
for (int j = 0; j < x.Length; j++)
{
byte a = x[x.Length - 1 - j];
byte b = y[y.Length - 1 - i];
c = (d + (a % 48) * (b % 48)) % 10;
array.Add((byte)c);
d = (d + (a % 48) * (b % 48)) / 10;
}
if (d > 0)
array.Add((byte)d);
result[i] = array;
}
for (int i = 0; i < result.Length; i++)
for (int j = 0; j < result[i].Count / 2; j++)
{
byte temp = result[i][j];
result[i][j] = result[i][result[i].Count - 1 - j];
result[i][result[i].Count - 1 - j] = temp;
}
if (result.Length > 1)
for (int i = 1; i < result.Length; i++)
for (int j = 0; j < result.Length - i; j++)
result[j + i].Add((byte)0);
if (result.Length > 1)
{
for (int i = 0; i < result.Length - 1; i++)
{
List<byte> z = result[0];
for (int j = 0; j < z.Count; j++)
z[j] += 48;
result[0] = new List<byte>(Encoding.Default.GetBytes(Addition(z.ToArray(), result[i + 1].ToArray())));
}
return Encoding.Default.GetString(result[0].ToArray());
}
return String.Join("", result[0]);
}
public static string Pow(string x, int degrees)
{
if (degrees == 0) return "1";
if (degrees == 1) return x;
byte[] result = Encoding.Default.GetBytes(x);
byte[] num = result;
for (int i = 2; i <= degrees; i++)
result = Encoding.Default.GetBytes(Multiplication(result, num));
return Encoding.Default.GetString(result);
}
public static string Factorial(int number)
{
if (number == 0) return "1";
if (number <= 2) return number.ToString();
byte[] result = Encoding.Default.GetBytes((6).ToString());
for (int i = 4; i <= number; i++)
result = Encoding.Default.GetBytes(Multiplication(result, Encoding.Default.GetBytes(i.ToString())));
return Encoding.Default.GetString(result);
}
}
Выше весь код до которого я додумался. И я уверен в том что этот код максимально плох.
Я хочу узнать чего нужно придерживаться когда пишешь такую библиотеку. (Например в чем хранить данные чтобы памяти меньше требовало или какие алгоритмы использовать для увеличения скорости работы) Желательно еще пару примеров. (Можно на любых языках) Ну и литературу какую-нибудь чтобы потом вопросов меньше задавать.
Я сам писал такое, могу дать следующие советы:
2^32
систему. Вместо массива байт число будет хранится в массиве uint
. При этом вы оптимально используете память, и все операции операции в этой системе счисления будут очень быстрыми. При этом парсинг строк и метод ToString
значительно усложнятся.BigInt
, тогда этого превращения не будет.O(n^2)
, умножение по алгоритму Карацубы работает за O(n^1.58)
. Вам нужно экспериментальным путем определить, при каких значениях длины умножаемых чисел следует использовать один алгоритм, а при каких другой.n
на число длиной m
, то результат будет не длиннее чем n + m
. Вы можете создать один массив такой длины и больше не создавать никаких объектов.Мой BigInteger: https://github.com/Zergatul/ZergatulLib/blob/master/Zergatul/Math/BigInteger.cs
Как-то мне тоже понадобилась длинная арифметика. Но использовать GMP было нельзя, так как длинная арифметика нужна была для микроконтроллеров без операционной системы и кучи. Пришлось написать свою библиотеку С++ шаблонов для работы с длинными целыми числами. Вот ссылка:
https://sourceforge.net/projects/muntl/?source=frontpage&position=5
Там в архиве есть и описание на русском языке.
Айфон мало держит заряд, разбираемся с проблемой вместе с AppLab
Сразу внесу ясность: добавление строки contextDatabase
У меня есть класс FurnitureComboBox, который является наследником ComboBoxПытаюсь привести ComboBox к FurnitureComboBox (от базового к производному) и чего-то не понимаю
Пытаюсь авторизоваться на сайте, но при решении ReCaptcha руками(ставиться пауза в скрипте), выводится ошибка "Повторите попытку"