squiggle.c

commit 92abecc65395099aa0d95270039ea42e5f6445db
parent 5f6cc0fe4f9e57744970f9b5e3bd9d78b28ef91d
Author: NunoSempere <nuno.sempere@protonmail.com>
Date:   Sat, 25 Nov 2023 21:28:43 +0000

start working on using quickselect instead of sorting

Diffstat:
M
squiggle_more.c
 | 
31
+++++++++++++++----------------

1 file changed, 15 insertions(+), 16 deletions(-)
diff --git a/squiggle_more.c b/squiggle_more.c
@@ -25,21 +25,11 @@ typedef struct ci_t {
     float low;
     float high;
 } ci;
-int compare_doubles(const void* p, const void* q)
-{
-    // https://wikiless.esmailelbob.xyz/wiki/Qsort?lang=en
-    double x = *(const double*)p;
-    double y = *(const double*)q;
-
-    /* Avoid returning x - y, which can cause undefined behaviour
-       because of signed integer overflow. */
-    if (x < y)
-        return -1; // Return -1 if you want ascending, 1 if you want descending order.
-    else if (x > y)
-        return 1; // Return 1 if you want ascending, -1 if you want descending order.
-
-    return 0;
-}
+typedef struct ci_searcher_t {
+    double num;
+    int remaining;
+} ci_searcher;
+
 ci get_90_confidence_interval(double (*sampler)(uint64_t*), uint64_t* seed)
 {
     int n = 100 * 1000;
@@ -47,7 +37,16 @@ ci get_90_confidence_interval(double (*sampler)(uint64_t*), uint64_t* seed)
     for (int i = 0; i < n; i++) {
         samples_array[i] = sampler(seed);
     }
-    qsort(samples_array, n, sizeof(double), compare_doubles);
+    // 10% confidence interval: n/20, n - n/20
+    ci_searcher low = {.x = samples_array[0], .remaining = n/20) };
+    ci_searcher high = {.x = samples_array[0], .remaining = n-(n/20) };
+
+    // test with finding the lowest
+    for(int j=1; i<n; j++){
+        if(low.x > samples_array[i]){
+            low.x = samples_array[i];
+        }
+    }
 
     ci result = {
         .low = samples_array[5000],