Здравствуйте. Пишу класс по учебе, суть: представить целые неотрицательные длинные числа, длиной до 100000 знаков (десятичных разрядов) и основные операции с ними (+,-,*,/,^,>,<,=). По сути уже написал, но возведение в степень работает слишком долго, не проходит по времени, в сравнении с питоновским n**n работает уж совсем долго, я не стремлюсь к питону, но ускорить необходимо. Пробовал решать в лоб: | Код |
mylong mtmp = m;
res.val[max-1] = 1;
while (mtmp.first != max-1 || mtmp.val[max-1] != 0) {
res = res * (*this);
if (res.error)
return res;
mtmp.decr();
}
|
Пробовал решать бинарным возведением в степень: | Код |
res.val[max-1] = 1;
mylong mt(m);
mylong tt(*this);
long long int n = mt.to_long();
for (;n > 0;n >>= 1) {
if (n & 1) {
res = res * tt;
if (res.error) return res;
}
tt = tt * tt;
if (tt.error) {
res.error = true;
return res;
}
}
|
Самое интересное, что первое работает быстрее  Ниже еще приведу свой класс целиком, кому не трудно, пожалуйста посмотрите, может посоветуете, как разогнать степень в такой реализации. Заранее спасибо большое! | Код |
#ifndef __calclib_h__
#define __calclib_h__
#define max 20001
class mylong {
private:
int val[max];
int first;
public:
bool error;
mylong();
mylong(const char *str);
mylong(const mylong &m);
int compare(const mylong &m); //0 - равны, 1 - аргумент меньше, -1 - аргумент больше
mylong operator +(const mylong &m);
mylong operator -(const mylong &m);
mylong operator *(const mylong &m);
mylong operator /(const mylong &m);
mylong operator ^(const mylong &m);
bool operator >(const mylong &m);
bool operator <(const mylong &m);
bool operator ==(const mylong &m);
long long int to_long();
void left_one(); //на 1 разряд влево сдвиг
mylong mult_by_int(int d); //домножить на 0 <= число <= 99999
void decr(); //декремент
void clear();
void print();
void fix_first();
~mylong();
};
#endif
|
| Код |
#include <stdio.h>
#include <limits.h>
#include "calclib.h"
mylong::mylong() {
for (int i = 0; i < max; i++)
val[i] = 0;
first = max - 1;
error = false;
}
mylong::mylong(const char *str) {
int len = 0;
while (str[len] != '\0') {
len++;
}
int k = max - 1;
int tmp, tmp2, cur = 0;
for (int i = 0; i < max; i++)
val[i] = 0;
for (int i = len - 1; i >= 0; i--) {
if (str[i] >= '0' && str[i] <= '9') {
tmp = val[k];
tmp2 = str[i] - '0';
for (int j = 0; j < cur; j++) tmp2 *= 10;
tmp += tmp2;
cur++;
if (tmp > 99999 || (cur == 6)) {
if (k == 0) {
printf("Error\n");
first = k;
fix_first();
return;
}
k--;
if (k < 0) {
printf("Error\n");
return;
}
cur = 1;
val[k] = str[i] - '0';
}
else {
val[k] = tmp;
}
}
else {
printf("Error\n");
first = k;
fix_first();
return;
}
}
first = k;
fix_first();
error = false;
}
mylong::mylong(const mylong &m) {
first = m.first;
for (int i = first; i < max; i++) {
val[i] = m.val[i];
}
error = m.error;
}
int mylong::compare(const mylong &m) {
if (first < m.first) return 1; //аргумент меньше
else if (first > m.first) return -1; //аргумент больше
else {
for (int i = first; i < max; i++) {
if (val[i] > m.val[i]) return 1;
else if (val[i] < m.val[i]) return -1;
}
return 0;
}
}
int min(int a, int b) {
if (a < b) return a;
else return b;
}
mylong mylong::operator +(const mylong &m) {
mylong res;
int k = max - 1;
int ost = 0;
while (k >= first || k >= m.first || ost != 0) {
res.val[k] += ost;
if (k >= first) res.val[k] += val[k];
if (k >= m.first) res.val[k] += m.val[k];
if (res.val[k] > 99999) {
res.val[k] -= 100000;
ost = 1;
}
else ost = 0;
k--;
if (k < 0) {
res.error = true;
return res;
}
}
res.first = k + 1;
if (first < 0) {
res.error = true;
return res;
}
res.error = false;
return res;
}
mylong mylong::operator -(const mylong &m) {
int test = compare(m);
mylong res;
int k = max - 1;
int ost = 0;
if (test >= 0) {
while (k >= first || ost != 0) {
if (k >= m.first) {
if ((val[k] - ost) < m.val[k]) {
res.val[k] = val[k] + (100000 - m.val[k] - ost);
ost = 1;
}
else {
res.val[k] = val[k] - m.val[k] - ost;
ost = 0;
}
k--;
}
else {
if ((val[k] - ost) < 0) {
res.val[k] = val[k] + (100000 - ost);
ost = 1;
}
else {
res.val[k] = val[k] - ost;
ost = 0;
}
k--;
}
}
res.error = false;
res.first = k + 1;
res.fix_first();
}
else res.error = true;
return res;
}
mylong mylong::operator *(const mylong &m) {
long long int mult;
mylong res;
mylong tmp;
int now = 0; //текущий разряд
int ost;
int k;
for (int i = max - 1; i >= m.first; i--) {
ost = 0;
k = max - 1;
while (k >= first || ost != 0) { //выполняем умножение 1ого числа на текущий разряд 2ого
if (k < first) mult = ost;
else mult = (long long int)m.val[i] * (long long int)val[k] + ost;
if (mult > 99999) {
ost = mult / 100000;
tmp.val[k] = mult - (ost * 100000);
}
else {
ost = 0;
tmp.val[k] = mult;
}
k--;
if (k < 0) {
res.error = true;
return res;
}
}
tmp.first = k+1;
if (first < 0) {
res.error = true;
return res;
}
tmp.fix_first();
tmp.first -= now;
if (first < 0) {
res.error = true;
return res;
}
//сдвиг разряда:
if (now) {
for (int k = tmp.first; k < max; k++) {
if (k >= max - now) tmp.val[k] = 0;
else tmp.val[k] = tmp.val[k+now];
}
}
now++;
tmp.fix_first();
//прибавление к общему результату:
res = res + tmp;
}
return res;
}
mylong mylong::operator ^(const mylong &m) {
mylong res;
if (val[max-1] == 0 && first == max-1 && m.val[max-1] == 0 && m.first == max-1) { //0^0
res.error = true;
return res;
}
if (m.val[max-1] == 0 && m.first == max-1) { //x^0
res.val[max-1] = 1;
return res;
}
if (val[max-1] == 0 && first == max-1) { //0^x
return res;
}
if (m.first < max - 4 || (m.first == max - 4 && m.val[m.first] > 9222)) { //переполнение long long int
res.error = true;
return res;
}
/*
mylong mtmp = m;
res.val[max-1] = 1;
while (mtmp.first != max-1 || mtmp.val[max-1] != 0) {
res = res * (*this);
if (res.error)
return res;
mtmp.decr();
}
*/
res.val[max-1] = 1;
mylong mt(m);
mylong tt(*this);
long long int n = mt.to_long();
for (;n > 0;n >>= 1) {
if (n & 1) {
res = res * tt;
if (res.error) return res;
}
tt = tt * tt;
if (tt.error) {
res.error = true;
return res;
}
}
return res;
}
mylong mylong::operator /(const mylong &m) {
mylong res; //результат
int cmp = compare(m);
if (cmp == -1) { //делитель > делимого
return res;
}
else if (cmp == 0) { //делитель = делимому
res.val[max-1] = 1;
return res;
}
if (m.val[max-1] == 0 && m.first == max-1) { //делить на 0 нельзя
res.error = true;
return res;
}
if (val[max-1] == 0 && first == max-1) { //нет смысла делить 0 на что-либо
return res;
}
mylong u, v = m; //делимое и делитель (временные)
mylong tmpu;
int k = first + 1; //текущий разряд делимого
int mult; //домножатель
u.val[max-1] = val[first]; //записываем первый разряд делимого во временное делимое
int q;
int r;
long long int tmp;
while (k <= max) {
while (v.compare(u) == 1) { //пока делитель больше делимого
if (k > max - 1) return res;
u.left_one(); //*100000
u.val[max-1] = val[k]; //дописываем по разряду
k++;
}
if (v.val[first] < 100000/2) { //проверка на необходимое условие
mult = 100000/(v.val[v.first] + 1);
tmpu = u;
u = u.mult_by_int(mult);
v = v.mult_by_int(mult); //и его исправление, если что
}
if (v.first == max - 1) { //у делителя всего 1 разряд
if (u.first == max - 1) { //и у делимого
q = u.val[u.first] / v.val[v.first];
}
else { //у делимого 2 разряда
tmp = (long long int)u.val[u.first]*100000 + (long long int)u.val[u.first+1];
q = tmp / (long long int)v.val[v.first];
}
}
else { //у делителя > 1 разряда
if (u.first == v.first) { //равное кол-во разрядов
q = min(u.val[u.first]/v.val[v.first], 100000-1);
r = u.val[u.first] - q*v.val[v.first]; //остаток
}
else { //у делимого > разрядов
q = min(((long long int)u.val[u.first]*100000 + (long long int)u.val[u.first+1]) / (long long int)v.val[v.first], 100000 - 1);
r = (long long int)u.val[u.first] * 100000 + u.val[u.first+1] - q*v.val[v.first]; //остаток
}
while ((r < 100000) && ((long long int)q * (long long int)v.val[v.first+1]) > ((long long int)r * 100000 + (long long int)u.val[u.first+1])) { //правим q, если нужно
q--;
r += v.val[v.first];
}
}
v = m;
v = v.mult_by_int(q);
u = tmpu - v;
v = m;
if (res.val[max-1] == 0 && res.first == max-1) {
res.val[max-1] = q;
}
else {
res.left_one();
res.val[max-1] = q;
}
}
return res;
}
bool mylong::operator >(const mylong &m) {
if (compare(m) == 1) return true;
else return false;
}
bool mylong::operator <(const mylong &m) {
if (compare(m) == -1) return true;
else return false;
}
bool mylong::operator ==(const mylong &m) {
if (compare(m) == 0) return true;
else return false;
}
long long int mylong::to_long() {
long long int res = 0;
for (int i = first; i < max; i++) {
res = res * 100000 + val[i];
}
return res;
}
void mylong::left_one() {
if (first == 0) {
error = true;
return;
}
first--;
for (int i = first; i < max - 1; i++) {
val[i] = val[i+1];
}
val[max-1] = 0;
}
mylong mylong::mult_by_int(int d) {
long long int mult;
mylong tmp;
int ost;
int k;
ost = 0;
k = max - 1;
while (k >= first || ost != 0) { //выполняем умножение инта на текущий разряд 2ого
if (k < first) mult = ost;
else mult = (long long int)d * (long long int)val[k] + ost;
if (mult > 99999) {
ost = mult / 100000;
tmp.val[k] = mult - (ost * 100000);
}
else {
ost = 0;
tmp.val[k] = mult;
}
k--;
}
tmp.first = k+1;
tmp.fix_first();
return tmp;
}
void mylong::clear() {
for (int i = 0; i < max; i++)
val[i] = 0;
first = max - 1;
error = false;
}
void mylong::decr() {
int k = max - 1;
while(1) {
if (val[k] - 1 < 0) {
val[k] = 100000 - 1;
k--;
}
else {
val[k]--;
break;
}
}
}
void mylong::fix_first() {
while(val[first] == 0 && first < max - 1) first++;
}
void mylong::print() {
int tmp, cc;
if (error) {
printf("Error\n");
return;
}
for (int k = first; k < max; k++) {
if (k != first) {
tmp = val[k];
cc = 5;
while (tmp != 0) {
tmp /= 10;
cc--;
}
for (int j = 0; j < cc; j++) printf("0");
}
if (cc != 5 && first != 0)
printf("%d", val[k]);
}
printf("\n");
}
mylong::~mylong() {
//нечего уничтожать
}
|
|
Длинная арифметика, Возведение в степень, время работы 
Загрузка ...
