6
\$\begingroup\$

I am relearning C so if you could point obvious faults in this solution to this problem I'd greatly appreciate such comments. Please note that I'm using GCC extensions to use larger than 32 bit numbers. Most importantly I want to be aware of the quality of memory management in particular.

http://news.ycombinator.com/item?id=3429466

#include <stdio.h>
#include <stdlib.h>

int64_t* next_pascal_row(int64_t* previous_row, int64_t previous_size)
{
  int64_t i;
  int64_t* retval;
  retval = (int64_t*)malloc(sizeof(int64_t)*(previous_size+1));
  for (i=0;i<previous_size+1;i++) {
    if (i==0 || i == previous_size) {
      retval[i] = 1;
    } else {
      retval[i] = previous_row[i-1] + previous_row[i];
    }
  }
  return retval;
}

void print_row(int64_t* row, int64_t size)
{
  int64_t i;
  for(i = 0; i < size; i++) {
    printf("%lld ",row[i]);
  }
  printf("\n");
}

int main()
{
  int64_t* first_row;
  int64_t* previous_row;
  int64_t* next_row;
  int64_t i,size;
  first_row = (int64_t*)malloc(sizeof(int64_t));
  first_row[0] = 1;
  size = 1;
  print_row(first_row,size);
  previous_row = first_row;
  for(i = 0; i<31;i++) {
    next_row = next_pascal_row(previous_row,size);
    size++;
    print_row(next_row,size);
    free(previous_row);
    previous_row = next_row;
  }
  free(next_row);
  return 0;
}
\$\endgroup\$
6
\$\begingroup\$

Looks pretty good to me. If I were doing this for an interview question, I would take on the challenge of implementing it recursively. Here are some minor changes I would make:

  1. You are hard-coding your for loop to 31 iterations. That ought to be a const uint32_t num_iterations = 31; at the top of your code. That makes it more clear to future users what to change if they want a different number of iterations.

  2. You are using int64_t. These are all going to be positive numbers, so uint64_t is more appropriate.

  3. Your variables i and size are int64_t. But your values are going to overflow 64-bits well before the line they are on gets that big. I'm guessing that uint32_t is enough.

  4. In regards to the memory management, all of the allocing and freeing is expensive and slow. If you wanted to minimize that, you should alloc 2 rows of max length up front and then ping-pong them as previous/next rows.

  5. In your next_pascal_row routine, you're using an array pointer called retval. I see that name way overused. It would be better called this_row or next_row.

  6. There is no need for a first_row pointer. Just use the previous_row pointer in initialization.

\$\endgroup\$
  • \$\begingroup\$ And on top of that, I should probably check the return value of malloc() for NULLness. As insightful as Paul's suggestions on reducing the algorithmic complexity are, I'm still choosing this answer for pointing out my failures to adhere to good C coding standards. \$\endgroup\$ – otto Jan 6 '12 at 16:25
5
\$\begingroup\$

int64_t is not a GCC extension; it comes from <stdint.h> (which you should #include to use).

All the values in a Pascal triangle are positive by definition, so you can fit in one extra bit, and calculate one further row before overflow, by using uint64_t instead of the signed int64_t.

There's no need to typecast the result of malloc() in C. It's an old and quirky tradition from 90s' language called "C/C++", but it doesn't fit in either proper C (because in C, void * is compatible with other pointer types) nor proper C++ (because in C++, you'd use new int[...] instead of malloc(...).)

I would suggest using for (...; i <= previous_size; ...) instead of i < previous_size + 1. One less operation makes the intent slightly easier for the human to read, and a loop to previous_size with previous_size included makes sense in the context.

I would take assigning the border values out of the loop, like this:

retval[0] = 1;
for (i = 1; i < previous_size; i++)
  retval[i] = previous_row[i - 1] + previous_row[i];
retval[previous_size] = 1;

Again, it reduces the number of moving parts, and makes the intent easier for human reader to track.

When iterating over each row, it's a bit of an overkill to use int64_t as the index. It doesn't exactly hurt (unless profiler tells you otherwise), but the middle numbers of the Pascal triangle grow very fast, and your signed 64-bit cells oveflow on the row with 68 cells on it, long before an ordinary int would run out of bits to index it. You can get to 69 if you use unsigned 64-bit cells.

Your main loop is a bit clumsy. You only need two pointers to rows rather than three, I would roll the loop a bit so that there's only one call to print_row(), and ith row is necessarily i cells long, so I would write it roughly like this instead:

int64_t *current_row;
int i; /* row counter and length of current_row */

current_row = malloc(sizeof(int64_t));
current_row[0] = 1;

for (i = 1; i <= 32; i++) {
  int64_t *next_row;
  print_row(current_row, i);
  next_row = next_pascal_row(current_row);
  free(current_row);
  current_row = next_row;
}

(You may, of course, disagree about combining i and size. It doesn't necessarily make sense in other potential similar contexts; it's just a property of the Pascal triangle.)

Because of the way C handles pointer variable declarations, I believe it makes more sense to place the star next to the variable's name, as in char *foo;, rather than next to the type, as in char* foo;. Even if you never declare more than one variable in a single declaration, it feels to me that this fits the spirit of C better.

\$\endgroup\$
  • \$\begingroup\$ Given that an exactly-64-bits type isn't required, you ought to recommend uint_fast64_t, or perhaps uint_least64_t (both of which <stdint.h> must provide, unlike uint64_t). uintmax_t would be another good choice, if the number of iterations can be made to match (e.g. using sizeof (uintmax_t) * CHAR_BIT). \$\endgroup\$ – Toby Speight Apr 3 '18 at 14:19
4
\$\begingroup\$

Rows of Pascal's triangle are palindromes, so if you add a count-down loop to print_row, you can get by with about half the calculations and half the memory.

Allocating 2 max length buffers and swapping re: @Luke is a good idea. But taking it one step further, you might get better memory cache performance if you interleaved the elements of the two current rows within a single allocated buffer. So, incrementing by 2 everywhere, you'd calculate something like

    row[i] = row[i-1] + row[i+1];

except to use that exact formula, you'd have to keep your "center" values rather than your edge values aligned at the same index -- like you would if you were drawing the triangle on paper. That's easier to do if you adopt the half-row optimization -- your "center" values can always be placed at the end or at the start of the vector, depending on whether you want to calculate the left half of the triangle growing backward/left or the right half of the triangle, growing forward/right.

OR I suppose you could get the same kind of interleaving and locality of reference with code that is much closer to your current code just by solely addressing even-indexed elements, incrementing by 2 and using

    this_row[i] = prev_row[i-2] + prev_row[i];

where this_row and prev_row swap values between row pointers that were initially set to be out of phase with each other:

    even_row = malloc(...); /* enough for two rows */
    odd_row = even_row+1;   /* even-indexed entries are now interleaved */

At some scales, you might even get better memory performance by calculating every other row in reverse order so you are initially operating on the same cached memory pages where you left off for the prior row.

\$\endgroup\$
2
\$\begingroup\$

Fix the compiler warnings

I get the following two warnings (after adding the necessary include of <stdint.h>):

7504.c: In function ‘next_pascal_row’:
7504.c:9:44: warning: conversion to ‘long unsigned int’ from ‘int64_t’ {aka ‘long int’} may change the sign of the result [-Wsign-conversion]
   retval = (int64_t*)malloc(sizeof(int64_t)*(previous_size+1));
                                            ^
7504.c: In function ‘print_row’:
7504.c:24:16: warning: format ‘%lld’ expects argument of type ‘long long int’, but argument 2 has type ‘int64_t’ {aka ‘long int’} [-Wformat=]
     printf("%lld ",row[i]);
             ~~~^   ~~~~~~
             %ld

The first is best fixed by using an unsigned type such as size_t for previous_size.

To fix the second, we can use one of the format macros in <inttypes.h>:

    printf("%"PRId64" ",row[i]);

Choose your element type

Entries will never be negative, so we can use an unsigned type, such as uint_least64_t. Even better, we can use a typedef so that it's clear where we're using this for the values in our triangle.

Always check your allocations succeed

When you use malloc() and family, you must check whether the returned pointer is null before using it. Also, there's no need to cast the return value (and doing so can sometimes mask errors you'll want to know about).

Don't allocate on every iteration

If you know in advance how many iterations you'll perform (as you do here), you can allocate two buffers big enough to hold all the values (i.e. one more than the iteration count), and swap between them at each iteration.

This change reduces allocations noticeably, from

total heap usage: 33 allocs, 33 frees, 5,248 bytes allocated

to

total heap usage: 3 allocs, 3 frees, 1,536 bytes allocated

Use const when reading

In next_pascal_row, we only read from previous_row, so we can pass it as a pointer to const numbers. Similarly, we can pass pointer-to-const into print_row().

Avoid testing for first and last in the loop

We're in control of the loop, so if we go from the second to the penultimate element, we can fill in the first and last values outwith the loop.


Modified code

#include <inttypes.h>
#include <limits.h>
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

typedef uintmax_t number;

void next_pascal_row(number *current,
                     const number *previous, size_t previous_size)
{
    current[0] = 1;
    for (size_t i = 1;  i < previous_size;  ++i) {
        current[i] = previous[i-1] + previous[i];
    }
    current[previous_size] = 1;
}

void print_row(const number *row, size_t size)
{
    for (size_t i = 0;  i < size;  ++i) {
        printf("%"PRId64" ", row[i]);
    }
    puts("");
}

int main()
{
    /* Estimate how many iterations we can have - conservatively
       assume that we double the middle value each round. */
    static const size_t iterations = sizeof (number) * CHAR_BIT;

    number *current_row = malloc(sizeof *current_row * iterations);
    number *previous_row = malloc(sizeof *previous_row * iterations);
    if (!current_row || !previous_row) {
        /* malloc failed */
        return 1;
    }

    for (size_t i = 0;  i < iterations;  ++i) {
        next_pascal_row(current_row, previous_row, i);
        print_row(current_row, i+1);
        /* now swap rows */
        number *next_row = previous_row;
        previous_row = current_row;
        current_row = next_row;
    }

    free(current_row);
    free(previous_row);
}
\$\endgroup\$
1
\$\begingroup\$

I don't know if your solution used memory allocation intentionally to practice that but if not, there is a much simpler solution to this problem. You can print the Pascal triangle with a simple 2 for loops over a 2D array. Sure, it takes 2 times the memory it actually needs but it will run faster and be less error prone, which is considered 'better' programming. (no risk for memory leakage or dangling pointers).

\$\endgroup\$
  • \$\begingroup\$ Hi, welcome to Code Review. Your answer came through the First Post review queue, but your answer does not review the code, it just provides a different solution. This is not a review, but, if you show how your code is different, and why your code is better, it will improve this answer. \$\endgroup\$ – Tunaki Mar 31 '16 at 8:36
  • \$\begingroup\$ @Tunaki I don't think this isn't a review. It passes all the points in this meta and actually explains why the proposed approach is better (although the reasons are controversial). \$\endgroup\$ – jacwah Mar 31 '16 at 8:59
  • \$\begingroup\$ Thank you @Tunaki for your comment. I will take it to accunt the next time I post an answer. Code snippet is a little difficult (or time consuming) through the android app but I will try to edit this when I get home. \$\endgroup\$ – bergerg Mar 31 '16 at 9:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.