From Newsgroup: comp.lang.c++

This is a reworked fun experiment I had about how to store and load data
in complex numbers:

https://groups.google.com/g/comp.lang.c++/c/bB1wA4wvoFc/m/OTccTiXLAgAJ



// updated code
Can you run it and tell me what you get? Thanks!

:^)
_____________________________________
// Chris M. Thomasson
// complex storage for fun...


#include <complex>
#include <iostream>
#include <vector>
#include <limits>
#include <algorithm>
#include <cstdint>
#include <cassert>
#include <cstring>

typedef std::int64_t ct_int;
typedef std::uint64_t ct_uint;
typedef double ct_float;
typedef std::numeric_limits<ct_float> ct_float_nlim;
typedef std::complex<ct_float> ct_complex;
typedef std::vector<ct_complex> ct_complex_vec;

#define CT_PI 3.14159265358979323846

ct_float
ct_roots(
ct_complex const& z,
ct_int p,
ct_complex_vec& out
) {
assert(p != 0);

ct_float radius = std::pow(std::abs(z), 1.0 / p);
ct_float angle_base = std::arg(z) / p;
ct_float angle_step = (CT_PI * 2.0) / p;

ct_uint n = std::abs(p);
ct_float avg_err = 0.0;

for (ct_uint i = 0; i < n; ++i) {
ct_float angle = angle_step * i;
ct_complex c = {
std::cos(angle_base + angle) * radius,
std::sin(angle_base + angle) * radius
};

out.push_back(c);

ct_complex raised = std::pow(c, p);
avg_err = avg_err + std::abs(raised - z);
}

return avg_err / n;
}

// Direct angular calculation - O(1) instead of O(n)
ct_int
ct_try_find_direct(
ct_complex const& z,
ct_complex const& z_next,
ct_int power,
ct_float eps
) {
// Calculate what the angle_base was when z_next's roots were computed
ct_float angle_base = std::arg(z_next) / power;

// Get z's angle relative to origin
ct_float z_angle = std::arg(z);

// Find which root slot z falls into
// Subtract the base angle and normalize
ct_float relative_angle = z_angle - angle_base;

// Normalize to [0, 2*pi)
while (relative_angle < 0) relative_angle += CT_PI * 2.0;
while (relative_angle >= CT_PI * 2.0) relative_angle -= CT_PI * 2.0;

// Calculate step size between roots
ct_float angle_step = (CT_PI * 2.0) / power;

// Find nearest root index
ct_uint index = (ct_uint)std::round(relative_angle / angle_step);

// Handle wrap-around
if (index >= (ct_uint)std::abs(power)) {
index = 0;
}

return index;
}

// Original linear search version - more robust but O(n)
ct_int
ct_try_find(
ct_complex const& z,
ct_complex_vec const& roots,
ct_float eps
) {
std::size_t n = roots.size();

for (std::size_t i = 0; i < n; ++i) {
ct_complex const& root = roots[i];
ct_float adif = std::abs(root - z);

if (adif < eps) {
return i;
}
}

return -1;
}

static std::string const g_tokens_str =
"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

ct_int
ct_gain_power(
std::string const& tokens
) {
ct_uint n = tokens.length();
std::size_t pmax = 0;

for (ct_uint i = 0; i < n; ++i) {
std::size_t fridx = g_tokens_str.find_first_of(tokens[i]);
assert(fridx != std::string::npos);
pmax = std::max(pmax, fridx);
}

return (ct_int)(pmax + 1);
}

ct_complex
ct_store(
ct_complex const& z_origin,
ct_int p,
std::string const& tokens
) {
ct_uint n = tokens.length();
ct_complex z = z_origin;
ct_float store_avg_err = 0.0;

std::cout << "Storing Data..." << "\n";
std::cout << "stored:z_origin:" << z_origin << "\n";

for (ct_uint i = 0; i < n; ++i) {
ct_complex_vec roots;
ct_float avg_err = ct_roots(z, p, roots);
store_avg_err = store_avg_err + avg_err;

std::size_t fridx = g_tokens_str.find_first_of(tokens[i]);
assert(fridx != std::string::npos);

z = roots[fridx];
std::cout << "stored[" << i << "]:" << z << "\n";
}

store_avg_err = store_avg_err / n;
std::cout << "store_avg_err:" << store_avg_err << "\n";

return z;
}

ct_float
ct_load(
ct_complex const& z_store,
ct_complex const& z_target,
ct_int p,
ct_float eps,
std::string& out_tokens,
ct_complex& out_z,
bool use_direct = false // Toggle between direct and linear search
) {
ct_complex z = z_store;
ct_uint n = 128;
ct_float load_err_sum = 0.0;

std::cout << "Loading Data... (using " << (use_direct ? "direct" : "linear search") << " method)\n";

for (ct_uint i = 0; i < n; ++i) {
// Raise to power to get parent point
ct_complex z_next = std::pow(z, p);

ct_int root_idx;

if (use_direct) {
// Direct O(1) calculation
root_idx = ct_try_find_direct(z, z_next, p, eps);
}
else {
// Linear search O(n) - compute roots and search
ct_complex_vec roots;
ct_float avg_err = ct_roots(z_next, p, roots);
load_err_sum += avg_err;
root_idx = ct_try_find(z, roots, eps);
}

if (root_idx < 0 || (ct_uint)root_idx >= g_tokens_str.length()) {
break;
}

std::cout << "loaded[" << i << "]:" << z << " (index:" <<
root_idx << ")\n";
out_tokens += g_tokens_str[root_idx];

// Move to parent point
z = z_next;

// Check if we've reached the origin
if (std::abs(z - z_target) < eps) {
std::cout << "fin detected!:[" << i << "]:" << z << "\n";
break;
}
}

// Reverse to get original order
std::reverse(out_tokens.begin(), out_tokens.end());
out_z = z;

return load_err_sum;
}

int main() {
std::cout.precision(ct_float_nlim::max_digits10);
std::cout << "g_tokens_str:" << g_tokens_str << "\n\n";

{
ct_complex z_origin = { -.75, .06 };
std::string stored = "CHRIS";
ct_int power = ct_gain_power(stored);

std::cout << "stored:" << stored << "\n";
std::cout << "power:" << power << "\n\n";
std::cout << "________________________________________\n";

// STORE
ct_complex z_stored = ct_store(z_origin, power, stored);

std::cout << "________________________________________\n";
std::cout << "\nSTORED POINT:" << z_stored << "\n";
std::cout << "________________________________________\n";

// LOAD - try both methods
std::string loaded;
ct_complex z_loaded;
ct_float eps = .001;

std::cout << "\n=== Testing LINEAR SEARCH method ===\n";
ct_float load_err_sum =
ct_load(z_stored, z_origin, power, eps, loaded, z_loaded,
false);

std::cout << "________________________________________\n";
std::cout << "\nORIGIN POINT:" << z_origin << "\n";
std::cout << "LOADED POINT:" << z_loaded << "\n";
std::cout << "\nloaded:" << loaded << "\n";
std::cout << "load_err_sum:" << load_err_sum << "\n";

if (stored == loaded) {
std::cout << "\n\nDATA COHERENT! :^D" << "\n";
}
else {
std::cout << "\n\n***** DATA CORRUPTED!!! Shi%! *****" << "\n";
std::cout << "Expected: " << stored << "\n";
std::cout << "Got: " << loaded << "\n";
}

// Try direct method
std::cout << "\n\n=== Testing DIRECT ANGULAR method ===\n";
std::string loaded_direct;
ct_complex z_loaded_direct;

ct_float load_err_sum_direct =
ct_load(z_stored, z_origin, power, eps, loaded_direct, z_loaded_direct, true);

std::cout << "________________________________________\n";
std::cout << "\nloaded:" << loaded_direct << "\n";

if (stored == loaded_direct) {
std::cout << "\n\nDATA COHERENT (DIRECT METHOD)! :^D" << "\n";
}
else {
std::cout << "\n\n***** DATA CORRUPTED (DIRECT METHOD)!!!
*****" << "\n";
std::cout << "Expected: " << stored << "\n";
std::cout << "Got: " << loaded_direct << "\n";
}
}

std::cout << "\n\nFin, hit <ENTER> to exit...\n";
std::fflush(stdout);
std::cin.get();

return 0;
}
_____________________________________


--- Synchronet 3.21a-Linux NewsLink 1.2