Оптимизация модуля большого умножения C++

Question

Я пытаюсь сделать свою программу, которая быстрее обрабатывает умножения больших чисел по модулю. Это мой текущий код:

#include <iostream> 
#include <stdio.h> 

using namespace std; 

int main() 
{ 
    long multiply = 1; 
    char x; 
    while ((x = getchar()) != '\n') 
    { 
     multiply = (multiply*(x-64))%26; 
    } 
    if (multiply < 10) 
     printf("0%d\n", multiply); 
    else 
     printf("%d\n", multiply); 
    return 0; 
} 

Answer 1

(Прежде всего, я получаю предупреждение, потому что вы используете символ %d для печати long, вероятно, вы можете просто использовать int, и это не будет иметь значения, так как максимальное значение is 26.)

Я думаю, что вы могли бы повысить скорость с помощью целого числа без знака, поскольку modulo немного проще для целых чисел без знака. (Трудно быть уверенным только в том, чтобы смотреть на сгенерированную сборку ... https://goo.gl/LAc42f)

Answer 2

Моя догадка getchar - это ваше узкое место. Вы можете попробовать чтения в больших кусков в то время:

#include <cstdio> 
#include <cctype> 

#define BUFFER 2048 
#define OFFSET ('A' - 1) 
#define MODULUS 26 

using namespace std; 

int main() 
{ 
    char buffer[BUFFER]; 
    int count, done = 0, multiply = 1; 
    while (!done && (count = fread(buffer, sizeof(char), BUFFER, stdin))) 
    { 
     for (int i = 0; i < count; i++) 
     { 
      if (isupper(buffer[i])) 
      { 
       multiply *= (buffer[i] - OFFSET); 
       multiply %= MODULUS; 
      } 
      else 
      { 
       done = 1; 
       break; 
      } 
     } 
    } 
    printf("%02d\n", multiply); 
    return 0; 
} 

фиксируется также вверх printf и удалены магические числа. Он работает с тестовыми примерами.

Один пункт отметить, что если вы получаете результат ноль после операции модуля, то нет смысла продолжать, потому что ваш продукт всегда будет равен нулю после этого, так что вы можете сделать ярлык там:

#include <cstdio> 
#include <cctype> 

#define BUFFER 2048 
#define OFFSET ('A' - 1) 
#define MODULUS 26 

using namespace std; 

int main() 
{ 
    char buffer[BUFFER]; 
    int count, done = 0, multiply = 1; 
    while (!done && multiply && (count = fread(buffer, sizeof(char), BUFFER, stdin))) 
    { 
     for (int i = 0; multiply && i < count; i++) 
     { 
      if (isupper(buffer[i])) 
      { 
       multiply *= (buffer[i] - OFFSET); 
       multiply %= MODULUS; 
      } 
      else 
      { 
       done = 1; 
       break; 
      } 
     } 
    } 
    printf("%02d\n", multiply); 
    return 0; 
} 

Чтение в кусках и оптимизация ярлыков может быть тем, что вам нужно, чтобы выиграть время.