Chris M. Thomasson
2017-06-18 23:11:30 UTC
The roots of complex numbers like z^n+c, or even just z^n can store
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
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