commit 8ab006560be10c051b4654f626edb26d1f668b47
parent 189878e99676b316362ff8f3ad0b9b611c210770
Author: quantumish <freifeld.david@gmail.com>
Date: Sat, 8 Aug 2026 15:44:03 -0700
Add old ML experiment in C and tweak docstrings
Diffstat:
| M | sha.cu | | | 2 | +- |
| A | yoctograd.c | | | 247 | +++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++ |
| M | zk-poly.c | | | 4 | ++-- |
3 files changed, 250 insertions(+), 3 deletions(-)
diff --git a/sha.cu b/sha.cu
@@ -4,7 +4,7 @@
* for a lot more optimization.
*
* The message schedules for the chunks processed by SHA256 are not sequentially
- * dependent and so this program generates them in parallel and then process them
+ * dependent and so this program generates them in parallel and then processes them
* sequentially when updating the hash.
*/
diff --git a/yoctograd.c b/yoctograd.c
@@ -0,0 +1,247 @@
+/* Editor's note: some experiments with minimalism in machine learning. This
+ * file is combined from a couple smaller files (none of which originally had
+ * comments).
+ *
+ * Written in the evening of August 2, 2022 after doing too much data science-y
+ * stuff in Python at work and craving some variety.
+ */
+
+#include <stdbool.h>
+#include <stdlib.h>
+#include <stdint.h>
+#include <stdio.h>
+#include <time.h>
+#include <string.h>
+
+// A tiny "autodiff library"
+
+typedef enum Op {
+ NIL, ADD, MUL, RLU,
+} Op;
+
+typedef struct __attribute__((__packed__)) Var {
+ float value;
+ float grad;
+ Op op; // TODO make uint8
+ struct Var* parents[2];
+} Var;
+
+Var* v_new(float value, Var* child_a, Var* child_b, Op op) {
+ Var* out = malloc(sizeof(Var));
+ out->value = value;
+ out->parents[0] = child_a;
+ out->parents[1] = child_b;
+ out->op = op;
+ return out;
+}
+
+#define v_add(a,b) v_new(a->value + b->value, a, b, ADD)
+#define v_mul(a,b) v_new(a->value * b->value, a, b, MUL)
+#define v_const(v) v_new(v, NULL, NULL, NIL)
+#define v_relu(v) v_new((v->value > 0) ? v->value : 0, v, NULL, RLU)
+
+void v_back(Var* v) {
+ if (v->op == ADD) {
+ v->parents[0]->grad += v->grad;
+ v->parents[1]->grad += v->grad;
+ } else if (v->op == MUL) {
+ v->parents[0]->grad += v->parents[1]->value * v->grad;
+ v->parents[1]->grad += v->parents[0]->value * v->grad;
+ } else if (v->op == RLU) {
+ v->parents[0]->grad += (v->value > 0) * v->grad;
+ }
+ if (v->parents[0] != NULL) v_back(v->parents[0]);
+ if (v->parents[1] != NULL) v_back(v->parents[1]);
+}
+
+// This is enough for a neural network! Disclaimer: This code is just a proof of
+// concept and is very silly (most notably it leaks tons of memory).
+
+typedef struct __attribute__((__packed__)) Neuron {
+ int16_t n_in;
+ Var* b;
+ Var** w;
+} Neuron;
+
+Neuron* neuron_new(uint16_t n_in, bool nonlin) {
+ Neuron* out = malloc(sizeof(Neuron));
+ out->w = malloc(n_in * sizeof(Var*));
+ for (uint16_t i = 0; i < n_in; i++) {
+ out->w[i] = v_const(.1*rand()/(float)RAND_MAX);
+ }
+ out->b = v_const(0);
+ out->n_in = n_in;
+ if (!nonlin) out->n_in = -out->n_in;
+ return out;
+}
+
+Var* neuron_forward(Neuron* n, Var** xs) {
+ Var* out = v_const(0);
+ for (uint16_t i = 0; i < n->n_in; i++) {
+ out = v_add(out, v_mul(n->w[i], xs[i]));
+ }
+ out = v_add(out, n->b);
+ if (n->n_in > 0) out = v_relu(out);
+ return out;
+}
+
+typedef struct Layer {
+ uint16_t sz;
+ Neuron** neurons;
+} Layer;
+
+Layer* layer_new(uint16_t n_in, uint16_t n_out) {
+ Layer* layer = malloc(sizeof(Layer));
+ layer->neurons = malloc(n_out * sizeof(Neuron));
+ for (uint16_t i = 0; i < n_out; i++) {
+ layer->neurons[i] = neuron_new(n_in, true);
+ }
+ layer->sz = n_out;
+ return layer;
+}
+
+Var** layer_forward(Layer* l, Var** xs) {
+ Var** out = malloc(l->sz * sizeof(Var*));
+ for (uint16_t i = 0; i < l->sz; i++) {
+ out[i] = neuron_forward(l->neurons[i], xs);
+ }
+ return out;
+}
+
+typedef struct Net {
+ uint16_t sz;
+ float lr;
+ Layer** layers;
+} Net;
+
+Net* net_new(uint16_t n_layers, float lr) {
+ Net* out = malloc(sizeof(Net));
+ out->layers = malloc(n_layers * sizeof(Layer*));
+ out->sz = n_layers;
+ out->lr = lr;
+ return out;
+}
+
+void net_update(Net* n) {
+ for (int i = 0; i < n->sz; i++) {
+ Layer* layer = n->layers[i];
+ for (int j = 0; j < layer->sz; j++) {
+ Neuron* neuron = n->layers[i]->neurons[j];
+ for (int k = 0; k < neuron->n_in; k++) {
+ #ifdef DEBUG
+ printf(
+ "Layer %d, neuron %d, weight %d has value %f and grad %f\n",
+ i, j, k,
+ neuron->w[k]->value,
+ neuron->w[k]->grad
+ );
+ #endif
+
+ neuron->w[k]->value -= neuron->w[k]->grad * n->lr;
+ }
+ #ifdef DEBUG
+ printf(
+ "Layer %d, neuron %d, bias has value %f and grad %f\n",
+ i, j,
+ neuron->b->value,
+ neuron->b->grad
+ );
+ #endif
+ neuron->b->value -= neuron->b->grad * n->lr;
+ }
+ }
+}
+
+void v_zero(Var* v) {
+ v->grad = 0;
+ if (v->parents[0] != NULL) v_zero(v->parents[0]);
+ if (v->parents[1] != NULL) v_zero(v->parents[1]);
+}
+
+Var** net_forward(Net* n, Var** inputs) {
+ Var** prev = inputs;
+ for (int i = 0; i < n->sz; i++) {
+ prev = layer_forward(n->layers[i], prev);
+ }
+ return prev;
+}
+
+float read_data_line(char* line, Var** inputs) {
+ int counter = 0;
+ float label;
+ char* pch = strtok(line, ",");
+ while (pch != NULL) {
+ if (counter == 4) {
+ label = strtof(pch, NULL);
+ } else {
+ inputs[counter]->value = strtof(pch, NULL);
+ }
+ pch = strtok(NULL, ",");
+ counter += 1;
+ }
+ return label;
+}
+
+int main() {
+ srand(time(NULL));
+ size_t EPOCHS = 100;
+ float LR = 0.0001;
+
+ Net* net = net_new(3, LR);
+ net->layers[0] = layer_new(4, 8);
+ net->layers[1] = layer_new(8, 8);
+ net->layers[2] = layer_new(8, 1);
+
+ Var** inputs = malloc(4 * sizeof(Var*));
+ for (int i = 0; i < 4; i++) inputs[i] = v_const(0.0);
+
+ size_t MAX_LINE = 64;
+ FILE* train = fopen("./train.txt", "r");
+ FILE* test = fopen("./test.txt", "r");
+ char* line = malloc(MAX_LINE * sizeof(char));
+ for (int i = 0; i < EPOCHS; i++) {
+ float total_loss = 0;
+ float total_val_loss = 0;
+ int train_lines = 0;
+ int test_lines = 0;
+
+ while (getline(&line, &MAX_LINE, train) != -1) {
+ float label = read_data_line(line, inputs);
+ Var* out = net_forward(net, inputs)[0];
+ Var* err = v_add(out, v_mul(v_const(-1), v_const(label)));
+ Var* loss = v_mul(err, err);
+ #ifdef DEBUG
+ printf(" batch | out: %f label: %f loss: %f\n",
+ out->value, label, loss->value);
+ #endif
+ total_loss += loss->value;
+ loss->grad = 1;
+ v_back(loss);
+ net_update(net);
+ v_zero(loss);
+ train_lines += 1;
+ }
+
+ while (getline(&line, &MAX_LINE, test) != -1) {
+ float label = read_data_line(line, inputs);
+ Var* out = net_forward(net, inputs)[0];
+ Var* err = v_add(out, v_mul(v_const(-1), v_const(label)));
+ Var* loss = v_mul(err, err);
+ total_val_loss += loss->value;
+ loss->grad = 1;
+ test_lines += 1;
+ }
+
+ fseek(train, 0, SEEK_SET);
+ fseek(test, 0, SEEK_SET);
+ printf("epoch %d/%zu: avg train loss of %f, avg val loss of %f\n",
+ i+1, EPOCHS, total_loss/train_lines, total_val_loss/test_lines);
+ }
+}
+
+// Watch the neural network train with something like the following:
+//
+// head -n 1096 ./data_banknote_authentication.txt > train.txt
+// tail -n 274 ./data_banknote_authentication.txt > test.txt
+// gcc yoctograd.c -o nn
+// ./nn
diff --git a/zk-poly.c b/zk-poly.c
@@ -1,5 +1,5 @@
-/* A hacky implementation of the "Non-Interactive Zero-Knowledge of a Polynomial" scheme
- * described in https://doi.org/10.48550/arXiv.1906.07221
+/* Editor's note: a hacky implementation of the "Non-Interactive Zero-Knowledge
+ * of a Polynomial" scheme described in https://doi.org/10.48550/arXiv.1906.07221
* Written during late October 2020.
*/
