Loading ...
Sorry, an error occurred while loading the content.

Re: [PrimeNumbers] [Fwd: Convolution Product in C++]

Expand Messages
  • Phil Carmody
    Here are some linting problems with the code. - You don t use all of the variables you have declared. - If your char buffer is 100 bytes long, the largest
    Message 1 of 2 , Jan 1, 2001
    • 0 Attachment
      Here are some 'linting' problems with the code.
      - You don't use all of the variables you have declared.
      - If your char buffer is 100 bytes long, the largest string that will fit in it is 99 bytes of digits, and 1 NUL at the end. Use [101] to house 100 digits.
      - You are also 'out by one' in some of your loops. With 100 digits, indices range from 0 to 99 inclusive.
      - Use of goto considered harmful. That's what do/for/while are for.

      Here are some simple optimisation hints:
      - you only use each component of the product twice, once to write to it, and once to read it. Why not calculate each product 'just in time'. Where you presently read the product simply do the calculation. Take care with the rectangular rather than square nature of the data.
      - You're only using <4 bits of each short anyway. Merge 4 bytes into a short. If you think you can access the 32*32->64 multiply instructions efficiently using your compiler then pack up to 9 bytes into a 32 bit int. The summing stage may get hairy if you chose to pack 9 bytes in, as the you musn't forget the carry.
      (8 works fine though). i.e. Work in base 10000 or 1000000000.

      Here are some trickier optimisations:
      - You could look into Karatsuba multiplication.

      Here is the handiest hint ever:
      - Just use someone else's pre-written libraries. Giants/giantint and GMP are excellent. The code I "wrote" to perform a Proth test was about 10 lines of real code using the GMP library.

      Sorry if this sounds critical, it's just that as my job for the last 2 years has been nothing but removing bugs in other peoples' code, I can't get out of the habit of analysing every piece of code I see.

      Phil


      On Mon, 01 January 2001, Milton Brown wrote:

      >
      > It is removing attachments?
      >
      > So here it is as text:
      >
      > Milton L. Brown
      > miltbrown@...
      >
      > //
      > // By Milton L. Brown 8-1-2000 (in file Mult.cpp)
      > // It takes two strings of numbers entered from the keyboard
      > // and converts each character to a short integer
      > // and multiplies the two strings for use in Number
      > // Theory Computation, uses Convolution Product
      >
      > #include <iostream.h>
      > #include <string.h>
      >
      > #define Short(x) (x-48)
      > // Character '0' corresponds to ASCII 48
      >
      > unsigned short int CharShort(char ch);
      > // This procedure changes a character to an unsigned short integer
      >
      > int Sum(char d[100]);
      > // This procedure computes the sum of the digits of the Number
      >
      > unsigned short int prod[101][101];
      > int sum[101][101];
      > int sum2[201];
      >
      > int N=0, M=0; // Global variable for string length
      >
      > int main()
      > {
      > char digits[100];
      > unsigned short int n[101], m[101];
      > unsigned short int prod[101][101];
      >
      > line1:
      > for (int t=0; t <101; t++) {
      > n[t] = 0; m[t] = 0; sum2[t] = 0; }
      > for (int i = 0; i <= 101; i++)
      > for (int j = 0; j <= 101; j++)
      > prod[i][j] = 0;
      >
      > cout << "Enter an integer upto 100 digits: "<< endl;
      > cin >> digits; // Reads digits upto 100
      > N = strlen(digits);
      > cout << " (" << N <<")"<< endl;
      > //Changes each character to a short integer
      > for (i = 0; i < N; i++)
      > n[i] = CharShort(digits[i]);
      >
      > cout << "Enter an integer upto 100 digits: "<< endl;
      > cin >> digits; // Reads digits upto 100
      > M = strlen(digits);
      > cout << " (" << M << ") " << endl;
      > //Changes each character to a short integer
      > for (int j = 0; j < M; j++)
      > m[j] = CharShort(digits[j]);
      >
      > for (i = 0; i < N; i++)
      > for (j = 0; j < M; j++)
      > prod[i][j] = n[i] * m[j];
      >
      > for ( int k = 0; k <= M+N-2; k++)
      > {
      > for (i = 0; i <= k; i++)
      > sum2[k] += prod[i][k-i];
      > cout << " " << sum2[k];
      > }
      > cout << " (" << M+N-1 << ") " << endl;
      >
      > for ( k = M+N-2; k >= 1; k--)
      > {
      > sum2[k-1] = sum2[k-1] + sum2[k]/10;
      > sum2[k] = sum2[k] %10;
      > }
      >
      > for ( k = 0; k <= M+N-2; k++)
      > cout << sum2[k];
      > cout << endl;
      > cout << endl;
      > goto line1;
      > return 0;
      > }
      >
      > unsigned short int CharShort(char ch)
      > {
      > return (ch-48);
      > }

      Mathematics should not have to involve martyrdom;
      Support Eric Weisstein, see http://mathworld.wolfram.com
      Find the best deals on the web at AltaVista Shopping!
      http://www.shopping.altavista.com
    Your message has been successfully submitted and would be delivered to recipients shortly.