previndexinfonext

code guessing, round #23 (completed)

started at ; stage 2 at ; ended at

specification

Euclid's on the horn; we'd better act fast. your challenge is to divide polynomials. submissions can be written in python, c, haskell, or any array language.

for any two univariate polynomials a and b, there are unique polynomials q and r such that a = bq + r and r is of a lower degree than q.

your challenge, given two polynomials, is to find q and r (Euclidean division). polynomials are represented as vectors like so:

-42      0      -12      1
-42x^0 + 0x^1 + -12x^2 + 1x^3
x^3 - 12x^2 - 42

for example:

a = [-42, 0, -12, 1], b = [-3, 1]

a = x^3 - 12x^2 - 42
b = x - 3

a = (x - 3)(x^2 - 9x - 27) + -123

q = [-27, -9, 1], r = [-123]

you may assume that all input values will be either positive zero or normal (not denormalized, infinite, NaN, or negative zero). you may also ignore the possibilty of over- or underflow while computing the result.

APIs:

results

  1. 👑 LyricLy +3 -1 = 2
    1. olus2000
    2. indigo (away until 9/26)
    3. Kestrel (was Olivia)
    4. GNU Radio Shows
    5. Olivia (was Kestrel)
  2. Olivia +3 -1 = 2
    1. Kestrel (was olus2000)
    2. indigo (away until 9/26)
    3. LyricLy
    4. GNU Radio Shows
    5. olus2000 (was Kestrel)
  3. olus2000 +1 -1 = 0
    1. Kestrel (was indigo (away until 9/26))
    2. indigo (away until 9/26) (was LyricLy)
    3. Olivia
    4. LyricLy (was GNU Radio Shows)
    5. GNU Radio Shows (was Kestrel)
  4. Kestrel +1 -1 = 0
    1. LyricLy (was olus2000)
    2. olus2000 (was indigo (away until 9/26))
    3. Olivia (was LyricLy)
    4. indigo (away until 9/26) (was Olivia)
    5. GNU Radio Shows
  5. indigo (away until 9/26) +1 -2 = -1
    1. LyricLy (was olus2000)
    2. Olivia (was LyricLy)
    3. GNU Radio Shows (was Olivia)
    4. olus2000 (was GNU Radio Shows)
    5. Kestrel
  6. GNU Radio Shows +0 -3 = -3
    1. indigo (away until 9/26) (was olus2000)
    2. Kestrel (was indigo (away until 9/26))
    3. Olivia (was LyricLy)
    4. olus2000 (was Olivia)
    5. LyricLy (was Kestrel)

entries

you can download all the entries

entry #1

written by olus2000
submitted at
0 likes

guesses
comments 3
razetime

Lyric has done this exact same thing before but without comments in cg #16 i think


olus2000

I'm sorry for this. I wanted to do something in APL but learning APL in one week while working didn't work out.


razetime

well you bamboozled me so good on you


post a comment


pure.hs ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
-- Code by SoundOfSpouting#6980 (UID: 151149148639330304)


entry = bigdiv -- Pointfree!!


bigdiv :: [Double] -> [Double] -> ([Double], [Double])
bigdiv [] _ = ([], [])
bigdiv (head : tail) b = do
    let (div, temp_mod) = bigdiv tail b
    let (x, mod) = smalldiv (head : temp_mod) b
    (x : div, mod)


smalldiv :: [Double] -> [Double] -> (Double, [Double])
smalldiv [] _ = (0, [])
smalldiv x [] = smalldiv x [0] -- Spot the zero division
smalldiv [a] [b] = (a/b, [])
smalldiv (a : ta) (b : tb) = do
    let (q, mod) = smalldiv ta tb
    (q, a - q * b : mod)

entry #2

written by indigo (away until 9/26)
submitted at
0 likes

guesses
comments 1
razetime

olus? I can only think that olus would write so much C code willingly


post a comment


main.c ASCII text
  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>

#include "polydivide.h"

// Prints a double array terminated by INFINITY
void print_array(double const *a) {
  putchar('{');
  for (; !isinf(*a); ++a) { printf(" %.2f", *a); }
  printf(" }");
}

// Compares using Total Squared Error; passes if error < tolerance
bool test(double const *a, double const *b, double const *expected_q,
          double const *expected_r, double const tolerance) {

  printf("\nTEST: a = ");
  print_array(a);

  printf(", b = ");
  print_array(b);
  putchar('\n');

  double *r;
  double *q = entry(a, b, &r);

  bool success = true;

  double error = 0;
  for (double const *qi = q, *eqi = expected_q; !isinf(*eqi); ++qi, ++eqi) {
    double const residual = *qi - *eqi;
    error += residual * residual;
  }
  if (error < tolerance) {
    printf("Q SUCCESS (error: %f): Q = ", error);
    print_array(q);
    putchar('\n');
  } else {
    printf("Q FAILED (error: %f): \n  EXPECTED: ", error);
    print_array(expected_q);
    printf("\n  GOT: ");
    print_array(q);
    putchar('\n');
    success = false;
  }

  error = 0;
  for (double const *ri = r, *eri = expected_r; !isinf(*eri); ++ri, ++eri) {
    error += (*ri - *eri) * (*ri - *eri);
  }
  if (error < tolerance) {
    printf("R SUCCESS (error: %f): R = ", error);
    print_array(r);
    putchar('\n');
  } else {
    printf("R FAILED (error: %f): \n  EXPECTED: ", error);
    print_array(expected_r);
    printf("\n  GOT: ");
    print_array(r);
    putchar('\n');
    success = false;
  }

  free(r);
  free(q);

  return success;
}

struct test_case {
  double const *a;
  double const *b;
  double const *expected_q;
  double const *expected_r;
};

int main(int argc, char const *argv[]) {
  double const tolerance = .000000001;

  struct test_case const test_suite[] = {
      // Basic tests
      {(double const[]){-42, 0, -12, 1, INFINITY},
       (double const[]){-3, 1, INFINITY},
       (double const[]){-27, -9, 1, INFINITY},
       (double const[]){-123, INFINITY}},

      {(double const[]){-21, -5, 4, INFINITY},
       (double const[]){-3, 1, INFINITY}, (double const[]){7, 4, INFINITY},
       (double const[]){0, INFINITY}},

      {(double const[]){12, 30, 40, INFINITY},
       (double const[]){1, 3, 4, INFINITY}, (double const[]){10, INFINITY},
       (double const[]){2, 0, INFINITY}},

      // Testing a case where the remainder isn't degree 0
      {(double const[]){-13, 2, -9, 0, 4, 2, INFINITY},
       (double const[]){1, -2, 1, INFINITY},
       (double const[]){11, 14, 8, 2, INFINITY},
       (double const[]){-24, 10, INFINITY}},

      // Testing a case that actually gives fractions
      {(double const[]){0, 0, 0, 1, INFINITY},
       (double const[]){1, -2, 3, INFINITY},
       (double const[]){2.0 / 9.0, 1.0 / 3.0, INFINITY},
       (double const[]){-2.0 / 9.0, 1.0 / 9.0, INFINITY}},

      // Testing a numerator with a lower degree than the denominator
      {(double const[]){1, 2, INFINITY},
       (double const[]){-3, 1, 2, 1, INFINITY}, (double const[]){INFINITY},
       (double const[]){1, INFINITY}},

      // Testing empty numerator
      {(double const[]){INFINITY}, (double const[]){-3, 1, INFINITY},
       (double const[]){INFINITY}, (double const[]){INFINITY}}};

  int const num_tests = sizeof test_suite / sizeof *test_suite;
  int num_success = 0;

  for (int test_index = 0; test_index < num_tests; ++test_index) {
    struct test_case const test_case = test_suite[test_index];

    num_success += test(test_case.a, test_case.b, test_case.expected_q,
                        test_case.expected_r, tolerance);
  }

  printf("\n%d of %d tests passed\n", num_success, num_tests);

  return 0;
}
polydivide.h ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
#ifndef POLYDIVIDE_H
#define POLYDIVIDE_H

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

// Takes two polynomials a, b, ordered in order of increasing power, terminated
// by INFINITY and a pointer to a pre-allocated remainder polynomial r.
// Allocates memory to q and r
double *entry(double const *a, double const *b, double **r) {
  // We first need to find the end of the polynomial
  // This is because polynomial division starts at the highest power
  // This also lets us compute the length of the polynomials,
  // important because we to compute the length of the quotient
  // to allocate memory for it.
  double const *a_end = a, *b_end = b;

  while (!isinf(*a_end)) { ++a_end; }
  while (!isinf(*b_end)) { ++b_end; }

  // The number of coeffients (excludes INFINITY terminator)
  // This is one more than the degree of the polynomial
  size_t const a_len = a_end - a;
  size_t const b_len = b_end - b;

  // Handle the numerator having lower degree than denominator
  if (a_len < b_len) {
    double *const q = malloc(1 * sizeof *q);
    *q = INFINITY;

    // Just create a copy of the numerator as the remainder
    *r = malloc((a_len + 1) * sizeof **r);
    memcpy(*r, a, (a_len + 1) * sizeof **r);

    return q;
  }

  size_t const q_len = a_len - b_len + 1;

  double *const q = malloc((q_len + 1) * sizeof *q);
  double *q_end = q + q_len;

  // Terminate the quotient polynomial
  *q_end = INFINITY;
  --q_end;

  // Move back to the coefficient before INFINITY
  --a_end;
  --b_end;

  // temporary values for computation
  double *temps = malloc(b_len * sizeof *temps);
  double *const temps_end = temps + b_len - 1;
  memcpy(temps, a_end - b_len + 1, b_len * sizeof *temps);

  // a_end - a + 1 = number of coefficients left in a
  while (a_end - a + 1 >= b_len) {
    double const a_lead = *temps_end;
    double const b_lead = *b_end;

    double const lead_factor = a_lead / b_lead;

    *q_end = lead_factor;

    // Recalculate temporaries
    // Basically subtracting b * lead_factor from temps,
    // shifting over by one,
    // and then getting the next coefficient from a
    double *tptr;
    double const *bptr;
    for (tptr = temps_end, bptr = b_end; tptr != temps; --tptr, --bptr) {
      *tptr = *(tptr - 1) - lead_factor * *(bptr - 1);
    }

    // Last iteration
    // Since it's the last iteration, there are no more coefficients in a
    if (a_end - a + 1 == b_len) {
      break;
    }

    *temps = *(a_end - b_len);

    --a_end;
    --q_end;
  }

  // Temps now basically contains the remainder, just needs some touching up
  // meaning shifting it over by one and adding the INFINITY terminator
  memmove(temps, temps + 1, (b_len - 1) * sizeof *temps);
  *temps_end = INFINITY;

  *r = temps;
  return q;
}

#endif

entry #3

written by LyricLy
submitted at
2 likes

guesses
comments 1
razetime

RocketRace antics..


post a comment


have_faith.c PC bitmap, Windows 98/2000 and newer format, 311 x 163 x 32, cbSize 791611963, bits offset 138

entry #4

written by Olivia
submitted at
1 like

guesses
comments 0

post a comment


457999277311131649+838851636221837394.txt ASCII text, with no line terminators
1
entry=:[: (}: ; {:) ([ (] -/@,:&}. (* {:)) ] , %&{.~)^:(>:@-~&#)&.|.~

entry #5

written by GNU Radio Shows
submitted at
1 like

guesses
comments 3
LyricLy

Jelly code in SBCS


razetime

Lyricly in real


Olivia

effervescent


post a comment


entry structured file

entry #6

written by Kestrel
submitted at
0 likes

guesses
comments 1
razetime

single comment. simplistic and inefficient spaghetti. Kestrel probably


post a comment


bogopolynomialdivide.py ASCII text
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
# bogopolynomialdivide
import struct
import random

def entry(a, b):
	"inefficient, also doesnt work in some cases because floating point but that isnt my fault"
	def l(p,x):
		if len(p)==1:return p*x
		else:return x*(p+l(p[:-1],x))
	while True:	
		p,q=[],[]
		for i in range(len(a)-len(b)):q+=struct.unpack('f',random.randbytes(4))
		for i in range(random.randint(len(a))):p+=struct.unpack('f',random.randbytes(4))
		e=1
		for i in range(500):
			x = struct.unpack('f',random.randbytes(4))
			if l(a,x)!=l(b,x)*l(p,x)+l(q,x):e=0
		if e>0.3409:return p,q
yiff.jpg JPEG image data, JFIF standard 1.01, aspect ratio, density 1x1, segment length 16, baseline, precision 8, 249x158, components 3