int main() { std::string QUICK = "WRITE A PROGRAM IN

>>55718545

multiply :: Integer -> Integer
multiply = (*)

>>55718545
Take your trash to the dpt where it doesn't shit up the front page

>>55718545

def programthatcalculatesproductoftwoarbitrarilylargestrings(x, y):
    return x * y

File: 1425029056511.png (42KB, 512x512px) Image search: [Google]

42KB, 512x512px

>>55718545
>>std::string
>>array of chars

>>55718578
This
>2016
>Using a language that doesn't support arbitrary precision numbers

>>55718545

> arbitrarily large on a finite amount of memory

>>55718568
oh noooooo, we won't have room for yet another battlestation thread!

>>55718545

var godBlessJS = (x,y) => x*y

>>55718545
>TWO ARBITRARILY LARGE DIGITS
>digits
I wouldn't call 0 to 9 "arbitrarily large"

Not going to attempt, R has no native support for arbitrary precision and the solution for this would be just copy/pasting the vignette for the Rmpfr package.

learn to be a better knifebird poster, OP

>>55718592
Dynamically allocated arrays are still arrays, bait-kun.

>>55718626
>2016
>not programming on a Turing machine

>>55718695
Finite-tape turing machines are still turing machines

>>55718695
std::string is more than a dynamically allocated array. Please read the STL sources again.

>>55718717
They are not computationally equivalent to unbounded Turing machines though. If the tape is bounded at both ends they're essentially just finite state automata.

File: 132624588973.png (239KB, 2550x3300px) Image search: [Google]

239KB, 2550x3300px

>>55718664
>R

File: 1459166594242.jpg (196KB, 700x700px) Image search: [Google]

196KB, 700x700px

let x y z = y * z

This is theoretically impossible. In order to calculate the memory necessary for the resulting string's length, an infinite amount of memory is necessary to store the length.

>>55719213
Not necessarily. At most the product of two numbers will have as many digits as the sum of the number of digits of two numbers. (When you multiply two digits together, you will never get above a four-digit number)

>>55719463
Yes necessarily. Assuming the numbers are of arbitrary size, meaning infinite, you would also require another infinite number to pre-allocate the memory. It's an infinite loop.

I guess you could just make the length an unsigned long long but that's not infinite.

>>55718611
it supports arbituary precision integers

>>55719516
Alright. You make a good point, but I was just referring to finite numbers (In the realm of hundreds of digits or so)

>>55719516
Wtf lol. You can't pass in a number of infinite size. The program has to get the number from somewhere.

>>55719593
>>55719607
These programming bird challenges are about programming, not mathematics. There is no limit in mathematics. But there is an absolute limit in programming. Consider the following:

class bigint
    int[] digits
    int size

Now we want to infinitely expand the digits array. Let's go buy infinite RAM. Still wouldn't work because the int of size limits the size.

class bigint
    int[] digits
    bigint size

Won't compile. No language accepts this. The compiler will go into an infinite recursion. Most compilers won't though, they'll just abort.

>>55719607
>You can't pass in a number of infinite size.

Yes, that's why the entire challenge is impossible. q.e.d.
Get fucked, stupid bird.

>>55719651
>int[] digits
>not std::vector<int>
nigga plz
also you'd only need a char in that.
also you could go with
unsigned long int size
which is max 0 to 18446744073709551615

>>55719463
>>55719516
>>55719607
>>55719651
The challenge asks for two digits, not two numbers. You can easily fit each of the two digits in a byte no matter what they are

>>55719719
Bird fucked up. New thread please.

>>55719651
Yes you can store and work operations on an infinitely sized number, assuming you have infinite memory and computational power. Store it in a full binary tree and if need be store the height of the tree in the same way.

>>55719772
Prove it faggot.

>>55719779
Have the leafs be ints. The nodes are classes containing the high and low halves of the nodes below it. Have you taken a basic structures class?

>>55719651
Yes, if you're trying to store the whole thing in-place.
But there's no reason you can't do it like a linked list:

struct IntDigit
    int this_digit
    IntDigit *next

>>55719950
How do you calculate the length of this struct?

>>55720005
It would be one int plus the word size, since it only contains a pointer to the next. Let's call this two words.
So every time you receive a new digit to add to the end of the number (if you got the number all at once, it would violate the no infinite numbers rule), you would just allocate 2 more words.

That being said, it would still be a shit to operate on mathematically. It would probably make more sense to receive the small end of the number first. Addition would be fairly easy, but multiplication would likely require some kind of index to keep track of where you are.

>>55720063
So you're saying you need an infinite int list to store the size of the infinite int list of the original number. How do you calculate the length of the infinite size list?

>>55720148
Why do you need to calculate or store the size of it?
I'm not saying to store the size of the original huge number in an IntDigit list, but to just use that for the number itself.

>>55720177
You need the size to do the final calculation or your list will get out of bound.

>>55718770
OP said
>favorite language

>>55720694
Not necesarily. You could do multiplication ad-hoc using a doubly-linked list so that you can traverse backwards
e.g. if your numbers are a[] and b[], then if a[0] and b[0] are the least significantly digits, then the result c[] becomes:
a[0] * b[0]; a[1] * b[0] + a[0] + b[1]; ... ; sum i from 0 to n (a[i] * b[n - i])
and then traverse one last time to do carry.
Except you don't actually need to have any iteration variable, you simply traverse the linked lists in a zig-zag fashion.

>>55718568
c=a*b

>>55718545

function CalcProduct(x, y)
    return x * y
end

:^)

>>55718545
>unused variable QUICK
>unused variable THREAT
Get stabbed, OP.

>>55718545
no idea how terribad the solution is but it seems to work, I'm probably really overcomplicating this

https://gist.github.com/anonymous/e515fcab8f358775790256f74d173c62

>>55718545
Here's a rather overcomplicated version for C, where each number is stored as a littleendian array of 32-bit integers, and the return is a pointer to an array storing the product. Returns null when multiplying by zero, just because. Max density, but max hassle.

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

uint32_t *multiply(uint32_t *a, uint32_t *b, int len_a, int len_b, int *len_prod)
{
    *len_prod = len_a+len_b;
    if (*len_prod < 1)
        return NULL;
    
    uint32_t *p = (uint32_t*) calloc(*len_prod, sizeof(uint32_t));
    if (p == NULL)
    {
        *len_prod = 0;
        return NULL;
    }
    uint64_t product = 0;
    for (int i = 0; i < len_a; i++)
    {
        for (int j = 0; j < len_b; j++)
        {
            product = ((uint64_t) a[i]) * ((uint64_t) b[j]);
            p[i + j] += (uint32_t) product;
            p[i + j + 1] += (uint32_t) (product >> 32);
        }
    }
    // Store in minimum length array
    int length = *len_prod;
    while(p[length - 1] == 0)
    {
        length--;
        if (length < 1)
        {
            free(p);
            return NULL;
        }
    }
    if (length != *len_prod)
    {
        *len_prod = length;
        void *q = realloc(p, length * sizeof(uint32_t));
        if(q == NULL)
        {
            free(p);
            return NULL;
        }
        p =  (uint32_t*) q;
    }
    return p;
}

>>55718545
>bc

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

int char_to_int(char x) {
  return (int) x - '0';
}

std::pair<int,int*> mul(char* x, char* y) {
  unsigned int len_x = strlen(x)
    , len_y = strlen(y)
    , carry = 0
    , len_total = len_x + len_y;
  int* ret = new int[len_total];
  for (int i = len_x-1; i >= 0; i--) {
    // carry = 0;
    int it = char_to_int(x[i]);
    for (int j = len_y-1; j >= 0; j--) {
      carry = 0;
      const int idx = i+j+1;
      ret[idx] += carry + it*char_to_int(y[j]);
      carry = ret[idx] / 10;
      ret[idx] %= 10;
    }
    ret[i] += carry;
  }
  return std::pair<int,int*>(len_total, ret);
}

char* multiply(char* x, char* y) {
  char *larger = NULL, * smaller = NULL;
  if (strlen(x) > strlen(y)) {
    larger = x;
    smaller = y;
  } else {
    larger = y;
    smaller = x;
  }
  std::pair<int, int*> res = mul(larger, smaller);
  char* ret = new char[res.first+1];
  int idx = 0;
  do {
    ret[idx] = res.second[idx] + '0';
    idx = idx + 1;
  } while (idx < res.first);
  ret[idx] = '\0';
  delete[] res.second;
  return ret;
}

int main(int argc, char** argv) {
  if (argc < 3) {
    puts("No.");
    return -1;
  }
  char* a = argv[1], * b = argv[2];
  char* res = multiply(a, b);
  printf("%s\n", res);
  delete[] res;
  return 0;
}

Sent from my iPhone

there we go

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

int char_to_int(char x) {
  return (int) x - '0';
}

std::pair<int,int*> mul(char* x, char* y) {
  unsigned int len_x = strlen(x)
    , len_y = strlen(y)
    , carry = 0
    , len_total = len_x + len_y;
  int* ret = new int[len_total];
  for (int i = len_x-1; i >= 0; i--) {
    carry = 0;
    int it = char_to_int(x[i]);
    for (int j = len_y-1; j >= 0; j--) {
      const int idx = i+j+1;
      ret[idx] += carry + it*char_to_int(y[j]);
      carry = ret[idx] / 10;
      ret[idx] %= 10;
    }
    ret[i] += carry;
  }
  return std::pair<int,int*>(len_total, ret);
}

char* multiply(char* x, char* y) {
  char *larger = NULL, * smaller = NULL;
  if (strlen(x) > strlen(y)) {
    larger = x;
    smaller = y;
  } else {
    larger = y;
    smaller = x;
  }
  std::pair<int, int*> res = mul(larger, smaller);
  char* ret = new char[res.first+1];
  int idx = 0;
  do {
    ret[idx] = res.second[idx] + '0';
    idx = idx + 1;
  } while (idx < res.first);
  ret[idx] = '\0';
  delete[] res.second;
  return ret;
}

int main(int argc, char** argv) {
  if (argc < 3) {
    puts("No.");
    return -1;
  }
  char* a = argv[1], * b = argv[2];
  char* res = multiply(a, b);
  printf("%s\n", res);
  delete[] res;
  return 0;
}