Thursday, April 13, 2017

Digest for comp.lang.c++@googlegroups.com - 13 updates in 3 topics

Marcel Mueller <news.5.maazl@spamgourmet.org>: Apr 13 04:31PM +0200

AFAIK the address of an external symbol with static linkage can be used
as constexpr (e.g. a method reference as template parameter).
 
Is it also possible to import /absolute/ linker symbols this way?
 
Example
 
shader.o:
00000000 R shader
00000410 A shader_size
 
shader.h:
// import the shader symbol from shader.o, OK
extern unsigned shader[];
 
// Try to import shader_size - does not work
extern const int shader_size;
constexpr int shader_size_proxy = (int)&shader_size;
#define shader_size shader_size_proxy
 
// without constexpr
const int shader_size_proxy2 = (int)&shader_size;
#undef shader_size
#define shader_size shader_size_proxy2
 
 
The basic problem is that C++ only imports addresses but not absolute
values like the global symbol shader_size. And the following required
conversion from int* to int is no longer a valid constexpr.
 
Is there anything to come around this restriction?
 
 
Marcel
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 13 06:24PM +0200

On 13-Apr-17 4:31 PM, Marcel Mueller wrote:
> values like the global symbol shader_size. And the following required
> conversion from int* to int is no longer a valid constexpr.
 
> Is there anything to come around this restriction?
 
Why can't you just provide the definition in a header file?
 
 
Cheers!,
 
- Alf
Marcel Mueller <news.5.maazl@spamgourmet.org>: Apr 13 10:55PM +0200

On 13.04.17 18.24, Alf P. Steinbach wrote:
> Why can't you just provide the definition in a header file?
 
Of course, I can generate a matching header with hard coded constants.
But C++ compilation time on a Pi 1 is pure pain. So I favor just to link
the executable when the GPU code changes.
 
 
Marcel
Ian Collins <ian-news@hotmail.com>: Apr 14 10:14AM +1200

On 04/14/17 08:55 AM, Marcel Mueller wrote:
 
> Of course, I can generate a matching header with hard coded constants.
> But C++ compilation time on a Pi 1 is pure pain. So I favor just to link
> the executable when the GPU code changes.
 
Use a cross-compiler?
 
--
Ian
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 13 10:25AM -0700

On 4/12/2017 12:09 AM, Marcel Mueller wrote:
> ct_complex c = std::polar(radius, angle_base + angle);
> might do the job for you if it is appropriately optimized at your target
> platform. At least it is more readable.
 
Agreed. std::polar is easier to read, and can be faster.
 
 
>> return avg_err / n;
 
> Is there a reason why you calculated the /absolute/ floating point error
> rather than the RMS value as usual?
 
Not really. I just wanted to get a quick idea about the errors that are
going on.
 
> double. Since you are operating at the unit circle fixed point is no big
> deal. But reasonably implementing the transcendental functions is no fun
> either.
 
Right. I am going to use a high-precision floating point library in
later versions. 64-bit doubles are pretty good for this experimental phase.
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 13 10:28AM -0700

On 4/12/2017 5:57 AM, Manfred wrote:
> numerical algorithms to calculate both values simultaneously in
> significantly less time than the two separate calls.
> I think it is a pity that sincos() was not included (was it considered?)
 
That would have been a nice function to have.
 
> used on 32-bit x86
> - on x86_64 it requires more work, but still the core numerical
> algorithm (e.g. a Newton expansion) can be easily adapted to this.
 
Nice. Well, I think that std::polar has the best chance of using
sincos(). Need to check the implementation.
David Brown <david.brown@hesbynett.no>: Apr 13 08:19PM +0200

On 11/04/17 01:09, Chris M. Thomasson wrote:
> how to make it better, please? Thank you all for your time. The function
> at the heart of this is the function ct_roots that breaks apart a
> complex number into its n-ary roots. Here is the code:
 
<snip>
> ratio? Any ideas?
 
> Will post more context later on tonight or tommorw.
 
> :^)
 
There are, I think, two big issues here. First, you have started the
coding before really understanding the maths. Second, you can an
iterative algorithm in floating point arithmetic - the errors there will
always build up.
 
Finding the nth roots of a complex number z is easy in polar
coordinates. Express z = r.e^it, where r = abs(z). Find the real nth
root of r, call it q. All your complex roots of z will have this magnitude.
 
Then consider the angle. Your original angle is t. Let s = t / n.
This is the angle for your principle root, which is then q.e^is. All
your other roots are this principle root multiplied by the n roots of
unity, e^2iπ.(j/n) for j = 0 .. n-1.
 
This means that you can easily calculate all the nth roots of your
original number directly, rather than iteratively, and thus avoid any
cumulative floating point rounding errors.
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 13 11:38AM -0700

On 4/13/2017 11:19 AM, David Brown wrote:
> is the angle for your principle root, which is then q.e^is. All your
> other roots are this principle root multiplied by the n roots of unity,
> e^2iπ.(j/n) for j = 0 .. n-1.
 
Makes sense to me. Thank you. Will this have the precision that cos/sin
has? The higher the precision, the more data we can store in a complex
number. Also, for the ct_store function, link you said, I do not need to
return all of the roots. Just the n'th root. So I do not need to return
a vector of all the roots in the ct_store function. I need to make two
functions. One that returns all the roots, and one that returns a single
targeted root. Its easy, and should be done today. The parametric nature
can be exploited in ct_store. However, I am not sure how to avoid
returning all the roots in the ct_load function.
 
Thanks again David.
 
 
> This means that you can easily calculate all the nth roots of your
> original number directly, rather than iteratively, and thus avoid any
> cumulative floating point rounding errors.
 
I can make two functions. One for targeting the n'th root, and one that
returns all the roots. ct_store uses the targeted version, ct_load uses
the other one to lookup the correct symbol in the roots.
 
Any more very interesting thoughts? :^)
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 13 11:40AM -0700

On 4/13/2017 11:38 AM, Chris M. Thomasson wrote:
>> e^2iπ.(j/n) for j = 0 .. n-1.
 
> Makes sense to me. Thank you. Will this have the precision that cos/sin
> has?
 
raising e to gain the base angle, is very fast, and I need to test it to
see if I can store the same amount of data vs the slow trig version. If
I cannot, then the precision loss of the fast method should be closely
examined.
 
 
 
> The higher the precision, the more data we can store in a complex
> number.
[...]
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 13 11:48AM -0700

On 4/13/2017 11:19 AM, David Brown wrote:
 
>> :^)
 
> There are, I think, two big issues here. First, you have started the
> coding before really understanding the maths.
 
I am not a mathematician David! Fwiw, I thank you for your comments.
 
[...]
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 12 09:51PM -0700

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.
 
__________________________________________
// 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;
}
__________________________________________
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 13 07:52AM +0200

On 13-Apr-17 6:51 AM, Chris M. Thomasson wrote:
 
> 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.
 
Uhm, this sounds exquisitely without practical application. :)
 
 
Cheers!,
 
- Alf
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 13 09:24AM -0700

On 4/12/2017 10:52 PM, Alf P. Steinbach wrote:
>> symbol index to a root in the complex number z during iteration. For
>> loading data, it raises z back up through the root chain.
 
> Uhm, this sounds exquisitely without practical application. :)
 
Maybe... ;^)
 
Fwiw, I am currently experimenting with using the technique in fractal
encryption. The form used is z^n+c to load data, and (z-c)^(1/n) to
store data in its roots. I personally think its interesting how we can
store and load data using inverse iteration of an n-ary Julia set.
 
https://en.wikipedia.org/wiki/Julia_set#Using_backwards_.28inverse.29_iteration_.28IIM.29
You received this digest because you're subscribed to updates for this group. You can change your settings on the group membership page.
To unsubscribe from this group and stop receiving emails from it send an email to comp.lang.c+++unsubscribe@googlegroups.com.
Posted by at

No comments:

Post a Comment

Subscribe to: Post Comments (Atom)