Thursday, February 23, 2017

Digest for comp.lang.c++@googlegroups.com - 17 updates in 5 topics

"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Feb 23 05:34AM +0100

I decided to do a little challenge we used to give to the students in
Bodø in the mid 1990s: to implement a bignumber class and use it to
compute the Fibonacci sequence up to a ridiculous length.
 
Checking my results against a Python script to do the same (Python has a
built-in bignumber type that's used automatically) I found that
Fib[121], while correctly computed as bignum bits, was displayed
incorrectly as decimal. Strange. So I added checking of the last digit:
 
#include <p/expressive/using_weakly_all.hpp>
 
#include <p/cppx/value_types/Big_int.hpp>
$using_nested_namespace( progrock, cppx );
 
#include <iostream>
$using_weakly_all_from_ns( std );
 
$procedure show_fibonacci()
{
using cppx::Big_int;
 
$let_mutable a = Big_int{ 1 };
$let_mutable b = Big_int{ 0 };
$let_mutable last_digit_of_a = 1;
$let_mutable last_digit_of_b = 0;
 
for( $each i $in i_up_to( 123 ) )
{
$let next = a + b;
$let s = next.to_decimal();
$let last_digit_of_next = s.back() - '0';
cout << i << " - " << s << " or in hex: " << next.to_hex()
<< endl;
$hopefully( last_digit_of_next == (last_digit_of_a +
last_digit_of_b) % 10 )
or $fail( "Ooops, that last result had incorrect last
decimal digit..." );
a = b; b = next;
last_digit_of_a = last_digit_of_b; last_digit_of_b =
last_digit_of_next;
}
}
 
$just{ show_fibonacci(); }
 
The last few lines of the output when I run it:
 
114 - 483162952612010163284885 or in hex: 665050EED5966FB5AB95
115 - 781774079430987230203437 or in hex: A58C0EC9B9E4287BCE2D
116 - 1264937032042997393488322 or in hex: 10BDC5FB88F7A983179C2
117 - 2046711111473984623691759 or in hex: 1B1686E82495EC0AD47EF
118 - 3311648143516982017180081 or in hex: 2BD44CE3AD8D958DEC1B1
119 - 5358359254990966640871840 or in hex: 46EAD3CBD2238198C09A0
120 - 8670007398507948658051921 or in hex: 72BF20AF7FB11726ACB51
121 - 14028385100242989008475377 or in hex: B9A9F47B51D498BF6D4F1
 
! show_fibonacci - Ooops, that last result had incorrect last
decimal digit...
 
Internally the number, at this point where things go wrong, has 3 32-bit
digits, and when the decimal presentation is /translated back/ to hex
it's correct except for the least significant hex digit of the most
significant 32-bit digit, which hex digit is 2 too large...
 
The to-decimal function is inefficient because it's just a way to get
decimals without using division, because I've not implemented division:
 
inline $function Big_int::to_decimal() const
-> string
{
$using_from_namespace( expressive, operator<< );
if( is_zero() ) { return "0"; }
else if( is_negative() ) { return "-"s <<
(-$self).to_decimal(); }
else
{
$let_mutable remaining = $self;
$let_mutable exponent = $lambda_using_references() -> int
{
$let_mutable power_of_ten = Big_int{1};
$let_mutable exp = 0;
while( power_of_ten <= remaining )
{
power_of_ten *= 10;
++exp;
}
return exp - 1;
}();
 
$let_mutable result = ""s;
while( exponent >= 0 )
{
$let power_of_ten = pow( Big_int{10}, exponent );
$let_mutable decimal_digit = 0;
while( decimal_digit*power_of_ten <= remaining )
{
++decimal_digit;
}
--decimal_digit;
result << char( '0' + decimal_digit );
$let k = remaining;
remaining -= decimal_digit*power_of_ten;
assert( remaining + decimal_digit*power_of_ten == k );
--exponent;
}
assert( remaining.is_zero() );
return result;
}
}
 
I can't see anything wrong, and (1) everything works just fine for the
first 121 Fibonacci numbers, and (2) the asserts don't trigger.
 
I'm baffled by my own bug.
 
Which is possibly in the subtraction operator or something, but I'm
exhausted & hungry; I'll eat and watch a movie, and see tomorrow if
anyone saw something blindingly obviously wrong?
 
 
Cheers!
 
- Alf
Ben Bacarisse <ben.usenet@bsb.me.uk>: Feb 23 02:42PM

> 121 - 14028385100242989008475377 or in hex: B9A9F47B51D498BF6D4F1
 
> ! show_fibonacci - Ooops, that last result had incorrect last
> decimal digit...
 
Not sure what all the $stuff is, but
 
fib(121) = 14028366653498915298923761
 
which differ from you decimal value of 14028385100242989008475377 by
18446744073709551616 which is 2^64. I.e. it's not just the last digit
(the hex value is correct).
 
> 32-bit digits, and when the decimal presentation is /translated back/
> to hex it's correct except for the least significant hex digit of the
> most significant 32-bit digit, which hex digit is 2 too large...
 
I didn't follow this.
 
> }
 
> I can't see anything wrong, and (1) everything works just fine for the
> first 121 Fibonacci numbers, and (2) the asserts don't trigger.
 
Maybe there is some carry propagation error where the addition in the
assert cancels the error from the subtraction. Do you subtract by
adding and fiddling the signs?
 
<snip>
--
Ben.
Mr Flibble <flibbleREMOVETHISBIT@i42.co.uk>: Feb 23 05:57PM

On 23/02/2017 04:34, Alf P. Steinbach wrote:
> return result;
> }
> }
 
All this $let_mutable and such bollocks makes your code harder to grok
than standard C++ so I have no interest in examining it and therefore
answering your questions about it.
 
/Flibble
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Feb 23 09:22PM +0100

On 23.02.2017 18:57, Mr Flibble wrote:
 
> All this $let_mutable and such bollocks makes your code harder to grok
> than standard C++ so I have no interest in examining it and therefore
> answering your questions about it.
 
Thanks, I think you're right about `$let_mutable`: it's too verbose by far.
 
The `$let` pseudo-keyword is shorter than the `auto const` that it
translates to, but `$let_mutable` is much longer than `auto`, just to
sort of press it into the same conceptual fold. It's idealism. Ungood.
 
I'm changing it to just `$var`, which is the conventional keyword for a
variable in JavaScript and C#.
 
#include <p/expressive/using_weakly_all.hpp>
 
#include <p/cppx/value_types/Big_int.hpp>
$using_nested_namespace( progrock, cppx );
 
#include <iostream>
$using_weakly_all_from_ns( std );
 
$procedure show_fibonacci()
{
using cppx::Big_int;
 
$var a = Big_int{ 1 };
$var b = Big_int{ 0 };
$var last_digit_of_a = 1;
$var last_digit_of_b = 0;
 
for( $each i $in i_up_to( 123 ) )
{
$let next = a + b;
$let s = next.to_decimal();
$let last_digit_of_next = s.back() - '0';
 
cout << i << " - " << s << " or in hex: " << next.to_hex()
<< endl;
$hopefully( last_digit_of_next == (last_digit_of_a +
last_digit_of_b) % 10 )
or $fail( "Ooops, that last result had incorrect last
decimal digit..." );
a = b; b = next;
last_digit_of_a = last_digit_of_b; last_digit_of_b =
last_digit_of_next;
}
}
 
$just{ show_fibonacci(); }
 
Cheers!, & thanks,
 
- Alf
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Feb 23 09:38PM +0100

On 23.02.2017 15:42, Ben Bacarisse wrote:
 
> which differ from you decimal value of 14028385100242989008475377 by
> 18446744073709551616 which is 2^64. I.e. it's not just the last digit
> (the hex value is correct).
 
Thank you that clarified things for me.
 
 
>> first 121 Fibonacci numbers, and (2) the asserts don't trigger.
 
> Maybe there is some carry propagation error where the addition in the
> assert cancels the error from the subtraction.
 
Yes, that sounds very likely.
 
 
> Do you subtract by adding and fiddling the signs?
 
Yes. I was lazy, didn't want to deal with carry.
 
inline $procedure Big_int::operator-=( ref_<const Big_int> other )
{
if( is_positive() != other.is_positive() )
{
$self += -other;
return;
}
 
$let n_digits_this = n_items_in( digits_ );
$let n_digits_other = n_items_in( other.digits_ );
$let n_operand_digits = max( n_digits_this, n_digits_other );
 
digits_.reserve( n_operand_digits + 1 );
 
// The following performs subtraction of the magnitudes. If
this produces
// a negative magnitude, then the original sign is flipped.
 
// Add ((a big power of R) - other), where R, the radix of the
numeral
// system used for digits_, is the number of possible digit values.
$let big_minus_one_minus_other = other.complemented_wrt(
n_operand_digits );
add( big_minus_one_minus_other, 1 );
 
// Subtract the big power of R that was added.
if( n_items_in( digits_ ) > n_operand_digits )
{
// The magnitude result is positive or 0.
assert( digits_.back() == 1 );
digits_.resize( n_operand_digits );
}
else
{
// The magnitude result is negative, but is brought to
positive by the
// big power of R.
 
// Compute (big - this), pretending to be positive for the
increment:
$let real_sign = exchange( is_negative_, false );
complement_wrt( n_operand_digits );
add( 1 );
// And then compute (this - big) =
is_negative_ = not real_sign;
}
remove_leading_zeroes();
}
 
The bignum state is a vector `digits_` and a boolean `is_negative_`, and
the representation is sign-and-magnitude, with zero as an empty vector
and `is_negative_` set to `false`.
 
`exchange` here is `std::exchange`. I learned about it just some months
back, so I feel that not every reader would be familiar with it.
 
I feel sure that your informed hunch is in the right direction, and it
should have nailed it down, but I still don't see where I go wrong...
 
 
Cheers!, and thanks,
 
- ALf
leigh.v.johnston@googlemail.com: Feb 23 01:26PM -0800

$var instead of auto? Why don't you like the auto keyword? Why do you prefer obfuscation to idiomatic C++? What you are doing try to make C++ code look like code from other inferior languages is really egregious.
thebtc@hotmail.com: Feb 23 11:34AM -0800

I am trying to find the eigenvalues of a square symmetric real matrix. I am supposed to use a lapacke routine for that. I have chosen to use the ssyev routine. I am now trying to write a .cc file that will calculate the eigenvalues of this matrix, however I don't understand the inputs for ssyev. I need the following:
 
jobz
uplo
n
a
lda
w
 
So far I have chosen the following:
 
char jobz = 'N'; // computes eigenvalues only
char uplo = 'U'; // stores the upper triangle of a in an array a
int n = 10; // the order of the matrix a
float a[] = [a 10 by 10 matrix which I will not copy-paste here] // the symmetric matrix a for which the eigenvalues will be found
int lda = n; // the leading dimension of the array a
float w = //
 
I don't know what the w is. Everywhere I looked it describes w as an output. But then I looked up lapack.h which I included at the top of my file and it has the following:
 
lapack_int LAPACKE_ssyev( int matrix_layout, char jobz, char uplo, lapack_int n, float* a, lapack_int lda, float* w );
 
so I need to be able to input something for w. But I don't know what that is. Any help would be much appreciated. Thanks!
scott@slp53.sl.home (Scott Lurndal): Feb 23 08:22PM

>nt n, float* a, lapack_int lda, float* w );
 
>so I need to be able to input something for w. But I don't know what that i=
>s. Any help would be much appreciated. Thanks!
 
LAPACKE_ssyev( ... , &w);
thebtc@hotmail.com: Feb 23 12:27PM -0800

@Scott Lurndal
> LAPACKE_ssyev( ... , &w);
 
Yes, but I write that part after the declarations. So I need to declare something for w, don't I? Otherwise my compiler will complain because w has been unassigned. So shouldn't I give it a value? I don't quite understand what it is. A document I read described it as all the eigenvalues that are outputted, so that means it shouldn't be an input but rather an output. So why it exists inside LAPACKE_ssyev( ... , &w); I don't understand.
 
Sorry, I'm very new to programming. I appreciate your time.
Ben Bacarisse <ben.usenet@bsb.me.uk>: Feb 23 08:52PM

> lapack_int n, float* a, lapack_int lda, float* w );
 
> so I need to be able to input something for w. But I don't know what
> that is. Any help would be much appreciated. Thanks!
 
w is a pointer to where the n eigenvalues are to be put. It's what is
sometimes called an "out" parameter. You don't need to give any values,
just enough space for the results to be recorded.
 
So, a is 10x10 which means w should be 10 floats:
 
float w[10];
 
Because of the way arrays work in C (which C++ inherited) the name of
an array will be converted to a pointer to its first element which is
exactly what is needed here:
 
LAPACKE_ssyev(..., w);
 
--
Ben.
ruben safir <ruben@mrbrklyn.com>: Feb 23 03:10PM -0500

On 02/21/2017 07:08 AM, Juha Nieminen wrote:
> You are comparing pointers, not values.
 
> Are you sure you didn't intend to write "*ptr1 == *ptr2"
> instead of "ptr1 == ptr2"?
 
 
that is a good suggestion, but I fixed this a week ago and forgot how I
fixed it already
"Rick C. Hodgin" <rick.c.hodgin@gmail.com>: Feb 23 08:11AM -0800

Real Troll wrote:
> rubbish on C newsgroup
 
> Rick C. Hodgin wrote:
> > What do you mean, "He destroyed Linux NG <alt.os.linux> completely...?"
 
I see what you mean now, RT.
 
Thank you,
Rick C. Hodgin
Christiano <christiano@engineer.com>: Feb 23 01:35AM -0300

I saw this Code in a book[1]:
 
Date next_Sunday(const Date &d)
{
// access d using d.day(), d.month(), and d.year()
// make new Date to return
}
 
But that sounded strange to me. I may be wrong, but creating an object
inside a function and then passing it through return forces the calling
function to make a copy of an object, if that object is large it can
make everything inefficient.
 
 
[1] http://stroustrup.com/Programming/
ISBN 978-0-321-99278-9
Programming: Principles and Practice using C++ (Second Edition)
In respect to the group and author:
I have the original book,
Using here only a little portion of the book for
educational/research purposes according to fair use.
Robert Wessel <robertwessel2@yahoo.com>: Feb 22 10:43PM -0600

On Thu, 23 Feb 2017 01:35:24 -0300, Christiano
> I have the original book,
> Using here only a little portion of the book for
> educational/research purposes according to fair use.
 
 
For such a thing, the common usage would probably be something like:
 
newdate = nextSunday(olddate);
 
Inlining that and replacing the object creation, copy, and destruction
with a direct update is a common optimization, for just that reason.
Of course the end result has to be the same as if all that had
actually happened.
"Alf P. Steinbach" <alf.p.steinbach+usenet@gmail.com>: Feb 23 05:46AM +0100

On 23.02.2017 05:35, Christiano wrote:
> inside a function and then passing it through return forces the calling
> function to make a copy of an object, if that object is large it can
> make everything inefficient.
 
Most every compiler nowadays applies Return Value Optimization if it
can. The comment in your code indicates that it can. Then the return
value is constructed directly in storage provided by the calling code,
instead of first being created as temporary and then copied or moved.
 
With C++17 it's possible that RVO will be required, not just permitted.
 
 
Cheers & hth.,
 
- Alf
Paavo Helde <myfirstname@osa.pri.ee>: Feb 23 11:10AM +0200

On 23.02.2017 6:35, Christiano wrote:
> inside a function and then passing it through return forces the calling
> function to make a copy of an object, if that object is large it can
> make everything inefficient.
 
1) A 'date' does not look like it could be large.
 
2) Compilers have been optimizing this kind of stuff for many years
(according to Wikipedia RVO was invented in 1991).
 
3) Since C++11, we also have rvalue references and move constructors &
assignments, which work best with temporaries like function return
values (otherwise you will need to pepper the code with unwanted noise
like std::move()).
 
4) If you want to make sure that no copies are made behind the curtains
you can mark the copy constructor and assignment deleted for the class
and rely on the move ctor/assignment instead. This coincidentally means
you should make use more of function return values, not less.
 
5) As you certainly know, premature optimization is the root of all
evil. Before reducing the readability and maintainability of your code
by doing manual "optimizations" which you *believe* should make the code
faster, take some time to actually *measure* it and see if your beliefs
have any ground.
Bo Persson <bop@gmb.dk>: Feb 23 01:50PM +0100

On 2017-02-23 05:35, Christiano wrote:
> inside a function and then passing it through return forces the calling
> function to make a copy of an object, if that object is large it can
> make everything inefficient.
 
Surely, the Date class isn't large.
 
You must also ask yourself how much "efficiency" you need in your
program, and if the date calculations make any difference.
 
My guess (just a guess, you have to measure to be sure) is that if you
do less than a million calculations per second, this function will not
show up in the profiler report.
 
And if you calculate next_Sunday more often than that, the real
optimization might be to ask yourself WHY? Could you perhaps calculate
it once, and reuse the value?
 
 
Bo Persson
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)