Chris M. Thomasson

2017-06-18 23:11:30 UTC

Permalink

The roots of complex numbers like z^n+c, or even just z^n can storeRaw Message

data. Fwiw, here is a quick and crude example of using the ct_roots

function described in the following thread:

"n-ary roots from complex numbers..."

https://groups.google.com/d/topic/comp.lang.c++/05XwgswUnDg/discussion

to actually store data. The following code stores my name "CHRIS" from

the following symbol table:

"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

in a single complex number via root map. For storing data, it maps each

symbol index to a root in the complex number z during iteration. For

loading data, it raises z back up through the root chain. Loading needs

the complex number, the origin number (for termination), and the correct

power, and it can recreate the stored data. It locates each root by

doing a little search in the n-ary roots returned by ct_roots. The

experimental function is ct_try_find. Take note of it because it is key

wrt being able to load the stored data... There has to be a more

efficient way of doing the root search. Humm... For termination, it

compares z iterates to the original number used for storing the information.

the function ct_store stores n-ary tokens in a single complex number.

the function ct_load loads n-ary tokens from a complex number.

The termination condition is iffy and really sensitive to floating point

errors. Its better to store data in strict blocks, so a load knows to

iterate a block length, and then quite. Now it has to compare the

iterates of z to the damn origin. Humm... The can be improved upon.

We cannot store too much data here, or one with get a data-incoherent

error, via assertion. I can store the symbols DEADBEEF for sure. ;^)

This is where floating point errors can really break things down.

Btw, I am wondering if you can run it and perhaps post some of the

output? It would be interesting to compare the results I get on to other

systems.

Before I go on, can anybody run this code? Also, I think this deserved

its own thread? Will get back to the group tomorrow.

Thanks everybody.

In C++:

__________________________________________

// 4/12/2017: n-ary complex storage example by Chris M. Thomasson

#include <complex>

#include <iostream>

#include <vector>

#include <limits>

#include <algorithm> // reverse

#include <cstdint> // want to work with 64-bit numbers

#include <cassert> // want to sanity check run time...

#include <cstring> // faster than iostream's?

// Well, I need some consistent typenames... ;^)

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::complex<ct_uint> ct_complex_uint;

typedef std::vector<ct_complex> ct_complex_vec;

#define CT_PI 3.14159265358979323846

// Round up and convert the real and imaginary

// parts of z to unsigned integers of type ct_uint

// return a complex number with unsigned integer parts

ct_complex_uint

ct_round_uint(

ct_complex const& z

) {

ct_uint re = (ct_uint)std::floor(std::abs(z.real()) + .5);

ct_uint im = (ct_uint)std::floor(std::abs(z.imag()) + .5);

return ct_complex_uint(re, im);

}

// the integer p shall not be zero

// create abs(p) roots of z wrt z^(1/p);

// store them in out, and return the average error.

ct_float

ct_roots(

ct_complex const& z,

ct_int p,

ct_complex_vec& out

) {

assert(p != 0);

// Gain the basics

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;

// Setup the iteration

ct_uint n = std::abs(p);

ct_float avg_err = 0.0;

// Calculate the n roots...

for (ct_uint i = 0; i < n; ++i)

{

// our angle

ct_float angle = angle_step * i;

// our point

ct_complex c = {

std::cos(angle_base + angle) * radius,

std::sin(angle_base + angle) * radius

};

// output data

out.push_back(c);

// Raise our root the the power...

ct_complex raised = std::pow(c, p);

// Sum up the Go% damn floating point errors!

avg_err = avg_err + std::abs(raised - z);

}

// gain the average error sum... ;^o

return avg_err / n;

}

// Try's to find the target root z out of roots using

// eps, return the index of the root, or -1 for failure.

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;

}

// The Token Table

// Will deal with scrambled token vectors in further posts.

// This is global for now, easy to convert to per store/load

// pairs

static std::string const g_tokens_str =

"0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";

// Gains the power from the largest token position

// from tokens in g_tokens_str

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);

}

// Store tokens using a power of p starting in z-origin

// Return the complex number holding said tokens.

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)

{

// Gain all of the roots, and running store error

ct_complex_vec roots;

ct_float avg_err = ct_roots(z, p, roots);

store_avg_err = store_avg_err + avg_err;

// reference our root

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;

}

// Load our tokens from z_store, power of p,

// stopping at z_target using eps, storing tokens

// in out_tokens, and the resulting z in out_z

ct_float

ct_load(

ct_complex const& z_store,

ct_complex const& z_target,

ct_int p,

ct_float eps, // epsilon

std::string& out_tokens,

ct_complex& out_z

) {

ct_complex z = z_store;

ct_uint n = 128; // max iter

ct_float load_err_sum = 0.0;

std::cout << "Loading Data..." << "\n";

for (ct_uint i = 0; i < n; ++i)

{

// raise...

ct_complex z_next = std::pow(z, p);

// Gain all of the roots, and running load error

ct_complex_vec roots;

ct_float avg_err = ct_roots(z_next, p, roots);

load_err_sum += avg_err;

// try to find our root...

int 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 << "\n";

out_tokens += g_tokens_str[root_idx];

// advance

z = z_next;

// check for termination condition...

if (std::abs(z - z_target) < eps)

{

std::cout << "fin detected!:[" << i << "]:" << z << "\n";

break;

}

}

// reverse our tokens

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 };

// The original data to be stored

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";

// The data loaded from the stored.

std::string loaded;

ct_complex z_loaded;

ct_float eps = .001; // epsilon

// LOAD

ct_float load_err_sum =

ct_load(z_stored, z_origin, power, eps, loaded, z_loaded);

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

std::cout << "\nORIGIN POINT:" << z_origin << "\n";

std::cout << "LOADED POINT:" << z_loaded << "\n";

std::cout << "\nloaded:" << loaded << "\n"

"load_err_sum:" << load_err_sum << "\n";

// make sure everything is okay...

if (stored == loaded)

{

std::cout << "\n\nDATA COHERENT! :^D" << "\n";

}

else

{

std::cout << "\n\n***** DATA CORRUPTED!!! Shi%! *****" << "\n";

assert(stored == loaded);

}

}

// Fin...

std::cout << "\n\nFin, hit <ENTER> to exit...\n";

std::fflush(stdout);

std::cin.get();

return 0;

}

__________________________________________

Fwiw, here are the outputs of the ct_store function I am getting from

two different compilers, MSVC and GCC:

MSVC 2015

________________________________________

Storing Data...

stored:z_origin:(-0.75,0.059999999999999998)

stored[0]:(-0.89756758958883731,0.41826246336621364)

stored[1]:(-0.8048304823068565,-0.59293470672819726)

stored[2]:(0.86792869817386908,-0.49666532554878623)

stored[3]:(-0.73820338609537295,-0.67457761324417354)

stored[4]:(0.95549545746010056,-0.29500576779591425)

store_avg_err:6.8460152306934853e-15

________________________________________

GCC version 5.1.0 (tdm64-1)

________________________________________

Storing Data...

stored:z_origin:(-0.75,0.059999999999999998)

stored[0]:(-0.89756758958883731,0.41826246336621364)

stored[1]:(-0.8048304823068565,-0.59293470672819726)

stored[2]:(0.86792869817386908,-0.49666532554878623)

stored[3]:(-0.73820338609537295,-0.67457761324417354)

stored[4]:(0.95549545746010056,-0.29500576779591425)

store_avg_err:6.8460152306934853e-15

________________________________________

If you run this and get different numbers, I would be interested in

looking at them. For instance, when this is executed online at:

http://cpp.sh I get:

________________________________________

Storing Data...

stored:z_origin:(-0.75,0.059999999999999998)

stored[0]:(-0.89756758958883731,0.41826246336621364)

stored[1]:(-0.8048304823068565,-0.59293470672819726)

stored[2]:(0.86792869817386908,-0.49666532554878623)

stored[3]:(-0.73820338609537295,-0.67457761324417354)

stored[4]:(0.95549545746010056,-0.29500576779591425)

store_avg_err:6.1392213260039921e-15

________________________________________

The store_avg_err is different!

Sorry for the crude nature of my technique. I am hoping readers here can

help me create a more concise, mathematical description.

thank you everybody.

Also, I am doing this in my free time. I wish I had more of it!

;^o