Monday, April 17, 2017

Digest for comp.lang.c++@googlegroups.com - 25 updates in 7 topics

"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.
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 11 12:13PM -0700

On 4/10/2017 10:41 PM, Christian Gollwitzer wrote:
> functions. Concerning accuracy, your algorithm is more accurate if you
> compute roots of very high order (say 1e10) - probably not for useful
> cases.
 
Here is a function I wrote that uses your algorithm:
_________________________________
ct_float
cg_roots(
ct_complex const& z,
ct_int p,
ct_complex_vec& out
) {
assert(p != 0);
 
/*
Per: Christian Gollwitzer's untested code at:
https://groups.google.com/d/msg/comp.lang.c++/05XwgswUnDg/gm_uqbcwAgAJ
 
std::vector<ct_complex> myroots;
ct_complex baseroot = std::pow(z, 1.0/p);
myroots.push_back(baseroot);
 
ct_complex root = baseroot;
ct_complex phasor = baseroot / std::abs(baseroot);
for (int i=1; i<n; i++) {
root *= phasor;
myroots.push_back(root);
}
*/
 
// Did I fuc% up his code! Read here:
 
ct_complex baseroot = std::pow(z, 1.0 / p);
out.push_back(baseroot);
 
ct_complex root = baseroot;
ct_complex phasor = baseroot / std::abs(baseroot);
 
ct_uint n = std::abs(p);
ct_float avg_err = 0.0;
 
for (ct_uint i = 1; i < n; ++i)
{
root *= phasor;
out.push_back(root);
 
// Raise our root the the power...
ct_complex raised = std::pow(root, p);
ct_complex_uint raised_rounded = ct_round_uint(raised);
 
// Output...
std::cout << "ct_roots_fast::raised[" << i << "]:" <<
raised << "\n";
std::cout << "ct_roots_fast::raised_rounded[" << i << "]:" <<
raised_rounded << "\n";
std::cout << "___________________________________\n";
 
// 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;
}
_________________________________
 
When I change the call in main to ct_roots to cg_roots in main wrt the
function in:
 
_________________________________
int main()
{
std::cout.precision(ct_float_nlim::max_digits10);
 
{
// Our origin point z
ct_complex z = { 94143178827, 0 };
 
std::cout << "z:" << z << " - " << std::abs(z) << "\n";
std::cout << "**********************************************\n\n";
 
// The call to ct_roots...
ct_complex_vec roots;
//ct_float avg_err = ct_roots(z, 23, roots);
ct_float avg_err = cg_roots(z, 23, roots);
std::cout << "\n\navg_err:" << avg_err << "\n";
 
// Output
std::cout << "___________________________________\n";
for (unsigned int i = 0; i < roots.size(); ++i)
{
ct_complex& root = roots[i];
 
std::cout << "root[" << i << "]:" << root << " - " <<
std::abs(root) << "\n";
}
std::cout << "___________________________________\n";
}
 
// Fin...
std::cout << "\n\nFin, hit <ENTER> to exit...\n";
std::fflush(stdout);
std::cin.get();
 
return 0;
}
_________________________________
 
 
I get the following incorrect output in the sense that it does show all
of the roots:
 
 
z:(94143178827,0) - 94143178827
**********************************************
 
ct_roots_fast::raised[1]:(94143178827,0)
ct_roots_fast::raised_rounded[1]:(94143178827,0)
___________________________________
ct_roots_fast::raised[2]:(94143178827,0)
ct_roots_fast::raised_rounded[2]:(94143178827,0)
___________________________________
ct_roots_fast::raised[3]:(94143178827,0)
ct_roots_fast::raised_rounded[3]:(94143178827,0)
___________________________________
ct_roots_fast::raised[4]:(94143178827,0)
ct_roots_fast::raised_rounded[4]:(94143178827,0)
___________________________________
ct_roots_fast::raised[5]:(94143178827,0)
ct_roots_fast::raised_rounded[5]:(94143178827,0)
___________________________________
ct_roots_fast::raised[6]:(94143178827,0)
ct_roots_fast::raised_rounded[6]:(94143178827,0)
___________________________________
ct_roots_fast::raised[7]:(94143178827,0)
ct_roots_fast::raised_rounded[7]:(94143178827,0)
___________________________________
ct_roots_fast::raised[8]:(94143178827,0)
ct_roots_fast::raised_rounded[8]:(94143178827,0)
___________________________________
ct_roots_fast::raised[9]:(94143178827,0)
ct_roots_fast::raised_rounded[9]:(94143178827,0)
___________________________________
ct_roots_fast::raised[10]:(94143178827,0)
ct_roots_fast::raised_rounded[10]:(94143178827,0)
___________________________________
ct_roots_fast::raised[11]:(94143178827,0)
ct_roots_fast::raised_rounded[11]:(94143178827,0)
___________________________________
ct_roots_fast::raised[12]:(94143178827,0)
ct_roots_fast::raised_rounded[12]:(94143178827,0)
___________________________________
ct_roots_fast::raised[13]:(94143178827,0)
ct_roots_fast::raised_rounded[13]:(94143178827,0)
___________________________________
ct_roots_fast::raised[14]:(94143178827,0)
ct_roots_fast::raised_rounded[14]:(94143178827,0)
___________________________________
ct_roots_fast::raised[15]:(94143178827,0)
ct_roots_fast::raised_rounded[15]:(94143178827,0)
___________________________________
ct_roots_fast::raised[16]:(94143178827,0)
ct_roots_fast::raised_rounded[16]:(94143178827,0)
___________________________________
ct_roots_fast::raised[17]:(94143178827,0)
ct_roots_fast::raised_rounded[17]:(94143178827,0)
___________________________________
ct_roots_fast::raised[18]:(94143178827,0)
ct_roots_fast::raised_rounded[18]:(94143178827,0)
___________________________________
ct_roots_fast::raised[19]:(94143178827,0)
ct_roots_fast::raised_rounded[19]:(94143178827,0)
___________________________________
ct_roots_fast::raised[20]:(94143178827,0)
ct_roots_fast::raised_rounded[20]:(94143178827,0)
___________________________________
ct_roots_fast::raised[21]:(94143178827,0)
ct_roots_fast::raised_rounded[21]:(94143178827,0)
___________________________________
ct_roots_fast::raised[22]:(94143178827,0)
ct_roots_fast::raised_rounded[22]:(94143178827,0)
___________________________________
 
 
avg_err:0
___________________________________
root[0]:(3,0) - 3
root[1]:(3,0) - 3
root[2]:(3,0) - 3
root[3]:(3,0) - 3
root[4]:(3,0) - 3
root[5]:(3,0) - 3
root[6]:(3,0) - 3
root[7]:(3,0) - 3
root[8]:(3,0) - 3
root[9]:(3,0) - 3
root[10]:(3,0) - 3
root[11]:(3,0) - 3
root[12]:(3,0) - 3
root[13]:(3,0) - 3
root[14]:(3,0) - 3
root[15]:(3,0) - 3
root[16]:(3,0) - 3
root[17]:(3,0) - 3
root[18]:(3,0) - 3
root[19]:(3,0) - 3
root[20]:(3,0) - 3
root[21]:(3,0) - 3
root[22]:(3,0) - 3
___________________________________
 
 
Fin, hit <ENTER> to exit...
 
 
 
 
Notice the roots are all (3, 0)? This is not correct. Please try to find
an error I may have created in my implementation of your code Christian
Gollwitzer, wrt the cg_roots function. Sorry if I fuc%ed it up man... ;^o
 
 
Fwiw, here is the output I get from using the original, slow trig
infested original of mine:
 
z:(94143178827,0) - 94143178827
**********************************************
 
ct_roots::raised[0]:(94143178827,0)
ct_roots::raised_rounded[0]:(94143178827,0)
___________________________________
ct_roots::raised[1]:(94143178826.999603,6.0557511273702414e-05)
ct_roots::raised_rounded[1]:(94143178827,0)
___________________________________
ct_roots::raised[2]:(94143178827.000259,-4.6116857044817097e-05)
ct_roots::raised_rounded[2]:(94143178827,0)
___________________________________
ct_roots::raised[3]:(94143178827.000259,-6.9175285567225643e-05)
ct_roots::raised_rounded[3]:(94143178827,0)
___________________________________
ct_roots::raised[4]:(94143178827.000259,-9.2233714089634195e-05)
ct_roots::raised_rounded[4]:(94143178827,0)
___________________________________
ct_roots::raised[5]:(94143178826.999603,-0.00044975590179648512)
ct_roots::raised_rounded[5]:(94143178827,0)
___________________________________
ct_roots::raised[6]:(94143178826.999603,-0.00013835057113445031)
ct_roots::raised_rounded[6]:(94143178827,0)
___________________________________
ct_roots::raised[7]:(94143178827.000259,-0.00016140899965685982)
ct_roots::raised_rounded[7]:(94143178827,0)
___________________________________
ct_roots::raised[8]:(94143178827.000259,-0.00018446742817926839)
ct_roots::raised_rounded[8]:(94143178827,0)
___________________________________
ct_roots::raised[9]:(94143178827.000259,-0.00087645337507056794)
ct_roots::raised_rounded[9]:(94143178827,0)
___________________________________
ct_roots::raised[10]:(94143178827.000259,-0.00089951180359297653)
ct_roots::raised_rounded[10]:(94143178827,0)
___________________________________
ct_roots::raised[11]:(94143178827.000259,0.00041528480462239701)
ct_roots::raised_rounded[11]:(94143178827,0)
___________________________________
ct_roots::raised[12]:(94143178827.000259,-0.00041528480462239701)
ct_roots::raised_rounded[12]:(94143178827,0)
___________________________________
ct_roots::raised[13]:(94143178827.000259,-0.0011072707515136966)
ct_roots::raised_rounded[13]:(94143178827,0)
___________________________________
ct_roots::raised[14]:(94143178826.999603,-0.00046140166166721089)
ct_roots::raised_rounded[14]:(94143178827,0)
___________________________________
ct_roots::raised[15]:(94143178827.000259,0.00018446742817926839)
ct_roots::raised_rounded[15]:(94143178827,0)
___________________________________
ct_roots::raised[16]:(94143178827.000259,-0.00050751851871203122)
ct_roots::raised_rounded[16]:(94143178827,0)
___________________________________
ct_roots::raised[17]:(94143178827.000259,-0.0005305769472344397)
ct_roots::raised_rounded[17]:(94143178827,0)
___________________________________
ct_roots::raised[18]:(94143178827.000259,-0.00088809913494129387)
ct_roots::raised_rounded[18]:(94143178827,0)
___________________________________
ct_roots::raised[19]:(94143178827.000259,-0.0012456213226481479)
ct_roots::raised_rounded[19]:(94143178827,0)
___________________________________
ct_roots::raised[20]:(94143178827.000259,-0.0012686797511705563)
ct_roots::raised_rounded[20]:(94143178827,0)
___________________________________
ct_roots::raised[21]:(94143178827.000259,4.6116857044817097e-05)
ct_roots::raised_rounded[21]:(94143178827,0)
___________________________________
ct_roots::raised[22]:(94143178827.000259,-0.00031140533066203698)
ct_roots::raised_rounded[22]:(94143178827,0)
___________________________________
 
 
avg_err:0.00056815732700208645
___________________________________
root[0]:(3,0) - 3
root[1]:(2.8887518620433976,0.80939031347107282) - 2.9999999999999996
root[2]:(2.5632582136394655,1.5587518501063007) - 3
root[3]:(2.0476594296559623,2.1925078928343722) - 3
root[4]:(1.3801951131934567,2.6636556552071258) - 3
root[5]:(0.61036803915790194,2.9372522630469682) - 2.9999999999999996
root[6]:(-0.20472724009401264,2.9930063075716173) - 2.9999999999999996
root[7]:(-1.0046388365129584,2.8267827663564615) - 3
root[8]:(-1.7300409663446012,2.4509096790313265) - 3
root[9]:(-2.3271338721132588,1.893263832978159) - 3
root[10]:(-2.7516339045163587,1.1952032695387254) - 3
root[11]:(-2.9720578381089924,0.40849994728873995) - 3
root[12]:(-2.9720578381089924,-0.40849994728873917) - 3
root[13]:(-2.7516339045163596,-1.1952032695387236) - 3
root[14]:(-2.3271338721132593,-1.8932638329781581) - 2.9999999999999996
root[15]:(-1.7300409663446015,-2.4509096790313261) - 3
root[16]:(-1.0046388365129593,-2.8267827663564611) - 3
root[17]:(-0.20472724009401405,-2.9930063075716173) - 3
root[18]:(0.61036803915789994,-2.9372522630469691) - 3
root[19]:(1.3801951131934547,-2.6636556552071267) - 3
root[20]:(2.0476594296559609,-2.1925078928343735) - 3
root[21]:(2.5632582136394655,-1.5587518501063007) - 3
root[22]:(2.8887518620433976,-0.80939031347107315) - 3
___________________________________
 
 
Fin, hit <ENTER> to exit...
 
 
The shows all of the roots. Yours only shows the primary root.
 
Please correct me if I am totally wrong.
 
;^o
Ralf Goertz <me@myprovider.invalid>: Apr 14 11:42AM +0200

Am Wed, 12 Apr 2017 14:57:52 +0200
> single call on platforms that allow that. This makes use of the power
> of numerical algorithms to calculate both values simultaneously in
> significantly less time than the two separate calls.
 
Do you know where I can read more about that efficient algorithm. Sine
being odd and cos even means that their Taylor serieses don't share
any common powers of x. So I am a bit puzzled how that is accomplished.
 
> be 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.
 
Hm, I just experimented a bit. Calculating 10 Million sines and cosine
separately takes as long as doing it in one go using sincos on my linux x86_64
architecture. Is it because the glibc sincos function is bogus here?
"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.
 
[...]
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.
bitrex <bitrex@de.lete.earthlink.net>: Apr 14 04:16PM -0400

On 04/14/2017 04:05 PM, bitrex wrote:
 
>> - Alf (baffled, again :) )
 
> e^(i*x) = cos(x) + i*sin(x).
 
> HTH ;)
 
The proof is, roughly speaking, given certain assumptions two functions
that are the homogeneous solution to the same linear ordinary
differential equation and have the same Taylor series coefficients over
some domain must be the same function.
 
Here the domain is actually the entire set of complex numbers, z, of
which the real numbers are a subset.
bitrex <bitrex@de.lete.earthlink.net>: Apr 14 04:05PM -0400

On 04/11/2017 02:23 AM, Alf P. Steinbach wrote:
> I've been thinking about this also in my younger days.
 
> Cheers!,
 
> - Alf (baffled, again :) )
 
e^(i*x) = cos(x) + i*sin(x).
 
HTH ;)
"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? :^)
Ralf Goertz <me@myprovider.invalid>: Apr 14 10:04AM +0200

Am Thu, 13 Apr 2017 10:28:02 -0700
 
> Nice. Well, I think that std::polar has the best chance of using
> sincos(). Need to check the implementation.
 
It doesn't use it here :-(
 
template<typename _Tp>
inline complex<_Tp>
polar(const _Tp& __rho, const _Tp& __theta)
{
__glibcxx_assert( __rho >= 0 );
return complex<_Tp>(__rho * cos(__theta), __rho * sin(__theta));
}
 
> g++ -v
Using built-in specs.
COLLECT_GCC=g++
COLLECT_LTO_WRAPPER=/usr/lib64/gcc/x86_64-suse-linux/6/lto-wrapper
Target: x86_64-suse-linux
Configured with: ../configure --prefix=/usr --infodir=/usr/share/info --mandir=/usr/share/man --libdir=/usr/lib64 --libexecdir=/usr/lib64 --enable-languages=c,c++,objc,fortran,obj-c++,java,ada,go --enable-offload-targets=hsa --enable-checking=release --with-gxx-include-dir=/usr/include/c++/6 --enable-ssp --disable-libssp --disable-libvtv --disable-libcc1 --enable-plugin --with-bugurl=http://bugs.opensuse.org/ --with-pkgversion='SUSE Linux' --disable-libgcj --with-slibdir=/lib64 --with-system-zlib --enable-__cxa_atexit --enable-libstdcxx-allocator=new --disable-libstdcxx-pch --enable-version-specific-runtime-libs --enable-linker-build-id --enable-linux-futex --enable-gnu-indirect-function --program-suffix=-6 --without-system-libunwind --enable-multilib --with-arch-32=x86-64 --with-tune=generic --build=x86_64-suse-linux --host=x86_64-suse-linux
Thread model: posix
gcc version 6.3.1 20170202 [gcc-6-branch revision 245119] (SUSE Linux)
Christian Gollwitzer <auriocus@gmx.de>: Apr 14 02:26PM +0200

Am 14.04.17 um 11:42 schrieb Ralf Goertz:
 
> Do you know where I can read more about that efficient algorithm. Sine
> being odd and cos even means that their Taylor serieses don't share
> any common powers of x. So I am a bit puzzled how that is accomplished.
 
There are ways to do it together, e.g. if an algorithm is involved which
is based upon rotation like CORDIC. Here is another paper:
https://arxiv.org/abs/cs/0406049
 
 
 
> Hm, I just experimented a bit. Calculating 10 Million sines and cosine
> separately takes as long as doing it in one go using sincos on my linux x86_64
> architecture. Is it because the glibc sincos function is bogus here?
 
1) sincos only exists in (deprecated) 8087 math, so the instruction is
no longer used for SSE math
 
2) Have you run the sin and cos in spearate loops or in two consecutive
lines? gcc may have optimized it to a single call to _sincos - check the
disassembly to be sure
 
Christian
Ralf Goertz <me@myprovider.invalid>: Apr 14 03:39PM +0200

Am Fri, 14 Apr 2017 14:26:07 +0200
 
> There are ways to do it together, e.g. if an algorithm is involved
> which is based upon rotation like CORDIC. Here is another paper:
> https://arxiv.org/abs/cs/0406049
 
Thanks, I'll have a look.

 
> 2) Have you run the sin and cos in spearate loops or in two
> consecutive lines? gcc may have optimized it to a single call to
> _sincos - check the disassembly to be sure
 
 
diff'ing the two assembler files I get:
 
< movl $_ZZ7mypolarIdESt7complexIT_ERKS1_S4_E1c, %esi
< movl $_ZZ7mypolarIdESt7complexIT_ERKS1_S4_E1s, %edi
1084c1082,1091
< call sincos
---
> call cos
> movq %xmm0, %rax
> movq %rax, _ZZ7mypolarIdESt7complexIT_ERKS1_S4_E1c(%rip)
 
So I guess g++ is not that clever. The function (mypolar) I used was
defined according to the std::polar function I posted elsewhere in this
thread:
 
template<typename T> inline complex<T> mypolar(const T& rho, const T& theta) {
static T s,c;
sincos(theta,&s,&c);
//s=sin(theta);
//c=cos(theta);
return complex<T>(rho*c,rho*s);
}
 
The 10 million runs of the loop take about 350 ms. The loop does nothing
but replacing the appropriate element of a vector<complex<double>> (vc)
with the result of the mypolar call:
 
for (auto &i:vc) {
i=mypolar(1.0,i.real());
}
 
I had placed [0, M_2_PI)-uniformly distributed angles into the real
components of the elements of vc beforehand.
David Brown <david.brown@hesbynett.no>: Apr 17 10:25PM +0200

On 13/04/17 20:38, 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?
 
Yes.
 
> The higher the precision, the more data we can store in a complex
> number.
 
Storing data in a floating point or complex number is possible in theory
with infinitely accurate real numbers - but totally and utterly useless
in practice. So don't worry about such details - if you think this is
fun to play with, then go ahead and play with it. Such experimentation
is fun and educational. Just don't be surprised when your double
precision numbers can't hold more than a couple of chars after manipulation.
 
> Also, for the ct_store function, link you said, I do not need to
> return all of the roots. Just the n'th root.
 
Doing the calculations in polar coordinates is perfect for this. You
can jump straight to the n'th root without going through any of the ones
in between.
 
David Brown <david.brown@hesbynett.no>: Apr 17 10:29PM +0200

On 13/04/17 20:48, Chris M. Thomasson 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.
 
No problem. As with many of your experiments, I cannot be optimistic
that you will get anything useful or practical in the end - but the
maths and the coding on the journey there can be fun and educational.
So enjoy the road, and don't feel disappointed about the destination.
 
<https://en.wikipedia.org/wiki/Complex_number#Polar_form>
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 17 02:53PM -0700

On 4/17/2017 1:29 PM, David Brown wrote:
 
>> I am not a mathematician David! Fwiw, I thank you for your comments.
 
> No problem. As with many of your experiments, I cannot be optimistic
> that you will get anything useful or practical in the end -
 
Totally fair enough. For instance, the size of the "ciphertext" wrt
storing the encoding of a plaintext in complex numbers is not all that
practical. However, it just might being useful in the sense of providing
security. Wrt somebody working in a niche field saying "I do not care
about the large ciphertext..."
 
 
> but the
> maths and the coding on the journey there can be fun and educational. So
> enjoy the road,
 
Oh the journey is very enlightening indeed! Coding the math is just
great and vise-versa. I have always thought is was neat when one of my
teachers accepted my homework as a series of little programs in
AppleSoft BASIC. Fwiw, this neat little site has an online emulator:
 
http://www.calormen.com/jsbasic
 
It brings back some memories.
 
 
> and don't feel disappointed about the destination.
 
Never. I need to hear from all the smart people out there. If you find
something iffy, let me know! I try to not get mad about being wrong, and
having to learn new things. Afaict, this is the essence of life!
Learning is fun, and a computer is a fun tool to have.
 
Thanks again David.
 
 
> <https://en.wikipedia.org/wiki/Complex_number#Polar_form>
 
Love the polar form. Can you think of a fast way to add two complex
numbers together in polar form? I always have to convert them back to
Cartesian to perform the addition. If this can be avoided, wrt gaining
the roots (z-c)^(1/n) from z^n+c, well, that would be great.
 
Converting back and forth between polar and Cartesian on every iteration
is very slow. Any more clever thoughts? :^)
Robert Wessel <robertwessel2@yahoo.com>: Apr 15 12:47AM -0500

On 14 Apr 2017 20:38:29 GMT, ram@zedat.fu-berlin.de (Stefan Ram)
wrote:
 
 
>sizeof instance.i
 
> should be just 1, because one byte is enough to store
> one out of 10 values.
 
 
While only a rough outline, a template with conversion operators, like
the following, should provide a start. This does require the actual
storage type to be explicitly specified, I'm not sure how you'd
generate that automatically from the range.
 
 
#include <stdexcept>
template<typename T, long MN, long MX>
class rangetype
{
T v;
void setv(long a)
{
if (a < MN || a > MX)
throw std::out_of_range("blah");
v=a-MN;
}
 
public:
rangetype& operator=(long a) {setv(a); return *this;}
operator long() {return v+MN;}
};
 
 
int main()
{
int a;
char b;
rangetype<char, 100, 200> q;
rangetype<int, 100, 2000> r;
 
q = 3;
q = 3.14;
 
a = q;
b = q;
 
r = q;
}
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Apr 14 11:57PM +0200

On 14-Apr-17 10:38 PM, Stefan Ram wrote:
 
> sizeof instance.i
 
> should be just 1, because one byte is enough to store
> one out of 10 values.
 
The problem is just all the boilerplate code to support arithmetic and
comparisons.
 
Boost has a little macro-based (I think it was) thing to generate that code.
 
 
Cheers!,
 
- Alf
Robert Wessel <robertwessel2@yahoo.com>: Apr 17 02:08AM -0500

On Sat, 15 Apr 2017 20:03:45 +0200, Winfied Valentin
> > ...
>> operator long() {return v+MN;}
 
>Why Du you substract MN? That's useless.
 
 
The OP wanted to store the range [2000000000..2000000010] in a single
byte.
Robert Wessel <robertwessel2@yahoo.com>: Apr 17 02:06AM -0500

On Sun, 16 Apr 2017 13:36:02 -0700, Tim Rentsch
>number of duplicate solutions (a factor of 8 factorial, IIANM).
>One easy way around that problem is to put the k'th queen in
>the k'th row, since any solution must have one queen in each row.
 
 
A better approach is to simply keep track of free rows, columns and
diagonals (both). One of the [rows,columns] gets handled by the
obvious loop (you don't try placing two queens on one of those). For
simplicity I'll assume columns. The others just need a bitmap for
each row or diagonal. There are 8* rows, and 15* (#rows*2-1)
diagonals in each of two directions.
 
Assume the columns are numbered 0-7, right-to-left, the rows 0-7,
top-to-bottom, and the diagonals (D1 and D2) are numbered 0-14,
top-to-bottom (D1 represents to upper-left to lower-right diagonals,
D2 the lower-left to upper-right). Assume you're working in column C,
and are attempting to place in queen in row R. You can just check the
row bitmap to check for a conflict on a row. You can trivially
compute the two diagonals the prospective queen is on (D1=(7-C)+R and
D2=C+R), and then just those two bits in each bitmap to check for
conflicts on the diagonals.
 
If you find a possible location, mark the appropriate row and (both)
diagonal bits, and move on to the next column. As you backtrack,
unmark the R/D1/D2 bits. Total storage is linear in the size of a
side of the board.
 
So you end up with something like:
 
 
Column[0..7] =0
Rbitmap[0..7]=0
D1bitmap[0..14]=0
D2bitmap[0..14]=0
 
main()
PlaceNextColumn(0)
 
PlaceNextColumn(C)
for(R=0..7)
Column[C]=R
Try(R,C)
 
Try(R,C)
D1=(7-C)+R
D2=C+R
if (Rbitmap[R]) return //conflict
if (D1bitmap[D1]) return //conflict
if (D2bitmap[D2]) return //conflict
// (no conflict)
Rbitmap[R]=1
D1bitmap[D1]=1
D2bitmap[D2]=1
if(C==7)
OutputSolution()
else
PlaceNextColumn(C+1)
Rbitmap[R]=0
D1bitmap[D1]=0
D2bitmap[D2]=0
 
OutputSolution()
printf("\nSolution: ")
for(C=0..7)
printf("Queen in column %i, on row %i ", C, Column[C])
 
 
 
*Assuming a standard chessboard - the approach generalizes to other
sizes, and rectangular boards
ram@zedat.fu-berlin.de (Stefan Ram): Apr 07 01:07PM

>missing memory. But is this the most specific sentence
>about the behavior of »push_back« (and similar functions)
>in the case of lack of (dynamic) memory in the standard?
 
Found this:
 
20.10.9 The default allocator [default.allocator]
...
20.10.9.1 allocator members [allocator.members]
...
T* allocate(size_t n);
...
4 Throws: bad_alloc if the storage cannot be obtained.
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 07 01:01PM -0700

On 4/6/2017 12:47 PM, Bonita Montero wrote:
>> I have tested them thoroughly and they are more stable and fast now.
 
> Don't trust in someone who claims to know how to write synchronization
> -facilities who doesn't even understand simple condidtion-variables.
 
Totally Agreed 100% Bonita!!!
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 07 01:00PM -0700

On 4/6/2017 3:13 PM, fir wrote:
> 1) you got much many cores there (even up to 10k parallel float channels there on the best cards)
> 2) heavy computational task concentrates in hot loops (thousands of parralel 'fibers' of the same computations not few of very different) and gpu model is more suitable for this
 
> if our idiot ramine will begin to write and optimise opencl kernels we could start talking
 
GPU is really suited for so-called embarrassingly parallel computations.
That's fine, and they really work well.
 
Fwiw, check this out, (needs WebGL):
 
http://funwithfractals.atspace.cc/ct_gfield_test/3d_user/ct_wormhole_exp.html
 
http://funwithfractals.atspace.cc/ct_gfield_test/ct_3dgfield_anime_test/
 
http://webpages.charter.net/appcore/fractal/webglx/ct_complex_field.html
(clicking on a part of the fractal will zoom in)
 
Love the GPU! Just love it.
 
:^D
"Chris M. Thomasson" <invalid@invalid.invalid>: Apr 14 10:45AM -0700

On 4/12/2017 9:51 PM, Chris M. Thomasson wrote:
 
> "n-ary roots from complex numbers..."
> https://groups.google.com/d/topic/comp.lang.c++/05XwgswUnDg/discussion
 
> to actually store data.
[...]
> 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.
[...]
 
> __________________________________________
[...]
> __________________________________________
 
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!
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)