Member Avatar for pestallozi 
a)         Write an algorithm to add and multiply two large integers, which cannot be 
represented by built-in types.
b)         Write a “c” function to find recursively the maximum and minimum element of 
    an array A of size “n” elements. Find also the number of comparisons required for 
this.





a)         Write an algorithm to add and multiply two large integers, which cannot be 
represented by built-in types.
b)         Write a “c” function to find recursively the maximum and minimum element of 
    an array A of size “n” elements. Find also the number of comparisons required for 
this.
  • 2 Contributors
  • 2 Replies
  • 129 Views
  • 4 Hours Discussion Span
  • Latest Post Latest Post by pestallozi

Dani AI

Generated

Two short, practical answers: represent big integers as strings (or as arrays of limbs) and implement grade‑school arithmetic for (a); for (b) ’s recursive approach is correct and simple but uses two comparisons per element — it can be improved.

A compact C implementation for nonnegative decimal strings (addition and schoolbook multiplication):

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

static char* str_dup(const char *s) {
    size_t n = strlen(s);
    char *r = malloc(n + 1);
    if (r) memcpy(r, s, n + 1);
    return r;
}

static void reverse_inplace(char *s) {
    size_t i = 0, j = strlen(s);
    if (j == 0) return;
    j--;
    while (i < j) { char t = s[i]; s[i] = s[j]; s[j] = t; i++; j--; }
}

char* big_add(const char *a, const char *b) {
    int ia = (int)strlen(a) - 1, ib = (int)strlen(b) - 1;
    int carry = 0, k = 0;
    char *tmp = malloc((size_t)( (ia>ib?ia:ib) + 3 ));
    if (!tmp) return NULL;
    while (ia >= 0 || ib >= 0 || carry) {
        int da = (ia >= 0) ? a[ia--] - '0' : 0;
        int db = (ib >= 0) ? b[ib--] - '0' : 0;
        int s = da + db + carry;
        tmp[k++] = '0' + (s % 10);
        carry = s / 10;
    }
    tmp[k] = '\0';
    reverse_inplace(tmp);
    return tmp;
}

char* big_mul(const char *a, const char *b) {
    if (a[0]=='0' && a[1]=='\0') return str_dup("0");
    if (b[0]=='0' && b[1]=='\0') return str_dup("0");
    int la = (int)strlen(a), lb = (int)strlen(b), n = la + lb;
    int *acc = calloc(n, sizeof(int));
    if (!acc) return NULL;
    for (int i = la - 1; i >= 0; --i) {
        int da = a[i] - '0';
        for (int j = lb - 1; j >= 0; --j) {
            int db = b[j] - '0';
            acc[i + j + 1] += da * db;
        }
    }
    for (int i = n - 1; i > 0; --i) { acc[i - 1] += acc[i] / 10; acc[i] %= 10; }
    int start = 0; while (start < n - 1 && acc[start] == 0) start++;
    char *res = malloc((size_t)(n - start + 1));
    for (int i = start; i < n; ++i) res[i - start] = '0' + acc[i];
    res[n - start] = '\0';
    free(acc);
    return res;
}

Performance and practical tips:

  • Addition is O(max(n,m)), multiplication above is O(n*m) time and O(n+m) memory. For very large inputs switch to limb arithmetic (base 1e9) and use 64‑bit intermediates; for asymptotically faster algorithms see Karatsuba (https://en.wikipedia.org/wiki/Karatsuba_algorithm) and FFT/Schönhage–Strassen methods.
  • Handle signs, leading zeros, input validation, and always check malloc returns.

Min/max comparisons:

  • ’s recursive routine makes 2 comparisons per recursive step -> total 2n - 2 comparisons for n>0.
  • A pairwise method reduces comparisons to about 1.5n: if n is even use 3n/2 - 2; if n is odd use 3*(n-1)/2. For example n=6: recursion ≈10 comparisons, pairwise ≈7.
Member Avatar for Gonbe

Example of b

#include <stdio.h>

int Highest (const int l, const int r)
{
    return ((l > r) ? l : r);
}

int Lowest (const int l, const int r)
{
    return ((l < r) ? l : r);
}

void FindMinMax (const int A[], const int n, int* const min, int* const max)
{
    int curMin = 0, curMax = 0;

    if (n == 1)
    {
        (*min) = A[0];
        (*max) = A[0];
    }
    else if (n > 1)
    {
        curMin = A[0];
        curMax = A[0];

        FindMinMax(A + 1, n - 1, min, max);

        (*min) = Lowest ((*min), curMin);
        (*max) = Highest((*max), curMax);
    }
}

int main(void)
{
    int example[] = { 23, 488, 1, 2930, 99, 102 };
    int low, high;

    FindMinMax(example, sizeof(example) / sizeof(int), &low, &high);
    printf("lowest: %d, highest: %d\n", low, high);

    return 0;
}

Found "a" too boring so didn't bother doing that.. Could maybe help if you start on it so I only have to finish/correct it.

commented: The OP's question falls under our homework rule. -2
commented: not even single effort seen , yet you give the code instead of advices +0
Member Avatar for pestallozi

Heeee! if you knew whom you are responding to, you wouldn't mind even teaching him 1+1 =2. I am a complete "newbie" to programming, started a few weeks ago. Its only that I am very much interested in grasping these things as much and as fast as I can. I know it takes time to learn, but I try!

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.