76 lines
2.6 KiB
Zig
76 lines
2.6 KiB
Zig
const std = @import("std");
|
|
|
|
fn findEntropy(fiboword: []const u8) f64 {
|
|
// Instead of using a hash map (like std::map in C++), using a flat
|
|
// array is extremely fast for mapping bytes to frequency counts.
|
|
var frequencies = [_]usize{0} ** 256;
|
|
for (fiboword) |c| {
|
|
frequencies[c] += 1;
|
|
}
|
|
|
|
const numlen: f64 = @floatFromInt(fiboword.len);
|
|
var infocontent: f64 = 0;
|
|
|
|
for (frequencies) |count| {
|
|
if (count > 0) {
|
|
const freq = @as(f64, @floatFromInt(count)) / numlen;
|
|
infocontent += freq * std.math.log2(freq);
|
|
}
|
|
}
|
|
|
|
// Multiply by -1 as in the original code
|
|
// Use `+ 0.0` trick to avoid negative zero (-0.0) if infocontent is 0
|
|
return -infocontent + 0.0;
|
|
}
|
|
|
|
fn printLine(writer: anytype, fiboword: []const u8, n: u32) !void {
|
|
const entropy = findEntropy(fiboword);
|
|
|
|
// Formatting equivalents:
|
|
// {d:<5} -> std::setw(5) << std::left << n
|
|
// {d:>12} -> std::setw(12) << std::right << fiboword.size()
|
|
// {d:<16.13} -> std::setw(16) << std::setprecision(13) << std::left << entropy
|
|
try writer.print("{d:<5}{d:>12} {d:<16.13}\n", .{ n, fiboword.len, entropy });
|
|
}
|
|
|
|
pub fn main() !void {
|
|
// A GeneralPurposeAllocator works perfectly for the large strings we will generate.
|
|
// Fib(37) string length expands to ~24 Megabytes.
|
|
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
|
|
defer _ = gpa.deinit();
|
|
const allocator = gpa.allocator();
|
|
|
|
const stdout = std.io.getStdOut().writer();
|
|
|
|
// Print header
|
|
try stdout.print("{s:<5}{s:>12} {s:<16}\n", .{ "N", "length", "entropy" });
|
|
|
|
// We start off by allocating the base strings on the heap so they
|
|
// can be naturally freed in the memory cycle below without compiler complaints.
|
|
var first: []const u8 = try allocator.dupe(u8, "1");
|
|
var n: u32 = 1;
|
|
try printLine(stdout, first, n);
|
|
|
|
var second: []const u8 = try allocator.dupe(u8, "0");
|
|
n += 1;
|
|
try printLine(stdout, second, n);
|
|
|
|
while (n < 37) {
|
|
// Concatenate `first` and `second` into a new allocated string
|
|
const result = try std.mem.concat(allocator, u8, &.{ first, second });
|
|
|
|
// C++ uses `.assign()`, which copies the string's characters.
|
|
// Here we can simply free the oldest string, step the slice references
|
|
// forward, and save execution time avoiding memory copy overhead!
|
|
allocator.free(first);
|
|
first = second;
|
|
second = result;
|
|
|
|
n += 1;
|
|
try printLine(stdout, result, n);
|
|
}
|
|
|
|
// Clean up our remaining two string references
|
|
allocator.free(first);
|
|
allocator.free(second);
|
|
}
|