Databases
StackOverflow2013
Postsdbo
PO
 

Note that there are some explanatory texts on larger screens.

plurals
  1. PO
    primarykey
    data
    text
    <p>It would be slightly easier if your digit-arrays were little-endian. Then your example multiplication would look</p> <pre><code> 3 2 1 * 6 5 --------------- 18 12 6 15 10 5 --------------- 18 27 16 5 // now propagate carries 8 28 16 5 8 8 18 5 8 8 8 6 ============ </code></pre> <p>The product of <code>n1[i]</code> and <code>n2[j]</code> would contribute to <code>result[i+j]</code>. The main loop could roughly look like</p> <pre><code>for (i = 0; i &lt; l1; ++i) // l1 is length of n1 { for (j = 0; j &lt; l2; ++j) // l2 is length of n2 { result[i+j] += n1[i]*n2[j]; } } // now carry propagation </code></pre> <p>You see that the result must be at least <code>(l1-1) + (l2-1) + 1</code> long, since the product of the most significant digits goes int <code>result[(l1-1) + (l2-1)]</code>. On the other hand, <code>n1 &lt; 10^l1</code> and <code>n2 &lt; 10^l2</code>, so the product is <code>&lt; 10^(l1+l2)</code> and you need at most <code>l1+l2</code> digits.<br> But if you're working with <code>char</code> (signed or unsigned), that will quickly overflow in each digit, since (for <code>k &lt;= min(l1-1,l2-1)</code>) <code>k+1</code> products of two digits (each can be as large as 81) contribute to digit <code>k</code> of the product.</p> <p>So it's better to perform the multiplication grouped according to the result digit, accumulating in a larger type, and doing carry propagation on writing the result digit. With little-endian numbers</p> <pre><code>char *mult(char *n1, size_t l1, char *n2, size_t l2, size_t *rl) { // allocate and zero-initialise, may be one more digit than needed char *result = calloc(l1+l2+1,1); *rl = l1 + l2; size_t k, i, lim = l1+l2-1; for (k = 0; k &lt; lim; ++k) { unsigned long accum = result[k]; for (i = (k &lt; l2) ? 0 : k-(l2-1); i &lt;= k &amp;&amp; i &lt; l1; ++i) { accum += (n1[i] - '0') * (n2[k-i] - '0'); } result[k] = accum % 10 + '0'; accum /= 10; i = k+1; while(accum &gt; 0) { result[i] += accum % 10; accum /= 10; ++i; } } if (result[l1+l2-1] == 0) { *rl -= 1; char *real_result = calloc(l1+l2,1); for (i = 0; i &lt; l1+l2-1; ++i) { real_result[i] = result[i]; } free(result); return real_result; } else { result[l1+l2-1] += '0'; return result; } } </code></pre> <p>For big-endian numbers, the indexing has to be modified - you can figure that out yourself, hopefully - but the principle remains the same.</p> <p>Indeed, the result isn't much different after tracking indices with pencil and paper:</p> <pre><code>char *mult(char *n1, size_t l1, char *n2, size_t l2, size_t *rl) { // allocate and zero-initialise, may be one more digit than needed // we need (l1+l2-1) or (l1+l2) digits for the product and a 0-terminator char *result = calloc(l1+l2+1,1); *rl = l1 + l2; size_t k, i, lim = l1+l2-1; // calculate the product from least significant digit to // most significant, least significant goes into result[l1+l2-1], // the digit result[0] can only be nonzero by carry propagation. for (k = lim; k &gt; 0; --k) { unsigned long accum = result[k]; // start with carry for (i = (k &lt; l2) ? 0 : k-l2; i &lt; k &amp;&amp; i &lt; l1; ++i) { accum += (n1[i] - '0') * (n2[k-1-i] - '0'); } result[k] = accum % 10 + '0'; accum /= 10; i = k-1; while(accum &gt; 0) { result[i] += accum % 10; accum /= 10; --i; } } if (result[0] == 0) // no carry in digit 0, we allocated too much { *rl -= 1; char *real_result = calloc(l1+l2,1); for (i = 0; i &lt; l1+l2-1; ++i) { real_result[i] = result[i+1]; } free(result); return real_result; } else { result[0] += '0'; // make it an ASCII digit return result; } } </code></pre> <p>Edit: added 0-terminators</p> <p>Note: these are not <code>NUL</code>-terminated <code>(unsigned) char</code> arrays, so we need to keep length information (that's good to do anyway), hence it would be better to store that info together with the digit array in a <code>struct</code>. Also, as written it only works for positive numbers. Dealing with negative numbers is awkward if you only have raw arrays, so another point for storing additional info.</p> <p>Keeping the digits as <code>'0' + value</code> doesn't make sense for the computations, it is only convenient for printing, but that only if they were <code>NUL</code>-terminated arrays. You may want to add a slot for the <code>NUL</code>-terminator then. In that case, the parameter <code>rl</code> in which we store the length of the product is not strictly necessary.</p>
    singulars
    1. This table or related slice is empty.
    1. POmultiply two arrays with int values
      singulars
      1. PTQuestion
    1. PTAnswer
    1. USDaniel Fischer
    1. USDaniel Fischer
    plurals
    1. This table or related slice is empty.
    1. This table or related slice is empty.
    1. POmultiply two arrays with int values
      singulars
      1. PTQuestion
    1. This table or related slice is empty.
    1. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTUpMod
    2. VO
      singulars
      1. PO
      1. This table or related slice is empty.
      1. VTAcceptedByOriginator
    1. CONice One! let me Try
      singulars
      1. PO
      1. USNickool
    2. COI'm not familiar with size_t does it need something like typedef unsigned int size_t;?should I call the size with something like sizeof?
      singulars
      1. PO
      1. USNickool
    3. CO`size_t` is a typedef'ed unsigned type, probably `unsigned long`. You can replace it with that. I don't understand the second question, the only type whose size matters here is (unsigned) char, and that's guaranteed to be 1.
      singulars
      1. PO
      1. USDaniel Fischer
 

Querying!

 
Guidance
A row detail

Detail views are divided into sections. All the information in the data section comes from columns in the selected row. The other sections display data from other, related rows.

Related data can be related in a to-one or a to-many fashion. Captions of data related in a to-many fashion link to a list view showing a filtered view of the table.

Try moving around until you find a non-empty to-many entry and click on the label to get to one. You can move back to the root by clicking on the database name in the header.

SQuiL has stopped working due to an internal error.

If you are curious you may find further information in the browser console, which is accessible through the devtools (F12).

Reload