Re: bigint and pow
On 10/2/22 09:24, Fausto via Digitalmars-d-learn wrote:
Thanks a lot. I am to used to C and, more important, I didn't think to look for
also another operator for the power function :)
Oh, and I forgot to mention that this is doing what you probably asked for
originally:
```d
import std;
import cmath = core.stdc.math;
void main()
{
// both print 1e+72
writeln(pow(10.0, 72));
writeln(cmath.pow(10, 72));
}
```
But it's just floating-point scientific notation, not true BigInts.
Another math difference from C is that D has well-defined wrapping math for
signed ints.
Re: bigint and pow
On 10/2/22 09:24, Fausto via Digitalmars-d-learn wrote:
Thanks a lot. I am to used to C and, more important, I didn't think to look for
also another operator for the power function :)
D does have pow and many other useful math functions [1], it's just not defined
for BitInts. Oh, and speaking of C, you also have access to all the usual C
math [1] functions with just an import:
```d
import std.stdio : writeln;
void main()
{
import std.math : pow;
writeln(pow(10, 3)); // pow from D
import core.stdc.math : pow;
writeln(pow(10, 3)); // pow from C
// can also make it more explicit to show where it is coming from:
import cmath = core.stdc.math;
writeln(cmath.pow(10, 3));
}
```
Have fun with D!
[1] https://dlang.org/library/std/math.html
[2] https://dlang.org/library/core/stdc/math.html
Re: bigint and pow
On Sunday, 2 October 2022 at 02:02:37 UTC, rassoc wrote:
On 10/2/22 00:04, Fausto via Digitalmars-d-learn wrote:
Hello,
I am trying to use pow with an integer argument, but I cannot
have a bigint result, for example, ```pow(10,72)```.
Do I have to write my pow function or is there a native
solution?
thanks,
Fausto
In contrast to certain scripting languages, there's no implicit
promotion, you have to opt in for BigInt [1] usage in D:
```d
import std;
void main()
{
// all print the same
writeln(BigInt(10) ^^ 72);
writeln(10.BigInt ^^ 72);
writeln("10".BigInt ^^ 72);
}
```
[1] https://dlang.org/phobos/std_bigint.html#.BigInt
Thanks a lot. I am to used to C and, more important, I didn't
think to look for also another operator for the power function :)
Re: bigint and pow
On 10/2/22 00:04, Fausto via Digitalmars-d-learn wrote:
Hello,
I am trying to use pow with an integer argument, but I cannot have a bigint
result, for example, ```pow(10,72)```.
Do I have to write my pow function or is there a native solution?
thanks,
Fausto
In contrast to certain scripting languages, there's no implicit promotion, you
have to opt in for BigInt [1] usage in D:
```d
import std;
void main()
{
// all print the same
writeln(BigInt(10) ^^ 72);
writeln(10.BigInt ^^ 72);
writeln("10".BigInt ^^ 72);
}
```
[1] https://dlang.org/phobos/std_bigint.html#.BigInt
bigint and pow
Hello, I am trying to use pow with an integer argument, but I cannot have a bigint result, for example, ```pow(10,72)```. Do I have to write my pow function or is there a native solution? thanks, Fausto
Re: BigInt and xor
On Tuesday, 24 March 2015 at 17:35:14 UTC, matovitch wrote: xor it with -1 instead of 1. (-1 is store as 0xfff..f with the classic modular arithmetic) Thanks.
Re: BigInt and xor
On Tuesday, 24 March 2015 at 17:28:50 UTC, Dennis Ritchie wrote: On Tuesday, 24 March 2015 at 16:35:04 UTC, Ivan Kazmenko wrote: What exactly is not working? Everything works. I'm just a little forgotten properties of the operation xor. I just wanted to xor 1 each digit in the number of type BigInt, while I would like to store each number in the binary representation of the array BigInt. xor it with -1 instead of 1. (-1 is store as 0xfff..f with the classic modular arithmetic)
Re: BigInt and xor
On Tuesday, 24 March 2015 at 16:35:04 UTC, Ivan Kazmenko wrote:
What exactly is not working?
Everything works. I'm just a little forgotten properties of the
operation xor.
I just wanted to xor 1 each digit in the number of type BigInt,
while I would like to store each number in the binary
representation of the array BigInt.
The only thing I see lacking is an ability to print a BigInt in
binary via writefln("%b").
Yes. It would be nice.
Up to 64 bits, arithmetic and bitwise operations, including
xor, are available with long and ulong. Just print the result
as binary:
-
import std.stdio;
void main() {
ulong n = ulong.max - 0b1000101;
writeln (n);
writefln ("%b", n);
writefln ("%b", n ^ 1);
}
-
Output:
-
18446744073709551546
10111010
10111011
-
If you need more than 64 bits, take a look at BitArray here, it
also has xor defined:
http://dlang.org/phobos/std_bitmanip.html#.BitArray
Thanks.
In the future, please explain what problem you are trying to
solve, as the wrong code alone often leaves one guessing.
OK, I will try.
Re: BigInt and xor
On Tuesday, 24 March 2015 at 15:45:36 UTC, Dennis Ritchie wrote:
Tell me, please, how can I replace this code?
import std.conv : to;
import std.bigint : BigInt;
import std.string : format;
import std.stdio : writeln;
void main() {
BigInt[10] bitArr;
ulong n = 18_446_724_073_709_551_614U;
bitArr[0] = format("%b", n).to!BigInt;
writeln(bitArr[0]);
writeln(bitArr[0] ^ 1); // not work
}
Output:
11101101110001100011000110101010
11101101110001100011000110101011
What exactly is not working?
The only thing I see lacking is an ability to print a BigInt in
binary via writefln("%b").
Up to 64 bits, arithmetic and bitwise operations, including xor,
are available with long and ulong. Just print the result as
binary:
-
import std.stdio;
void main() {
ulong n = ulong.max - 0b1000101;
writeln (n);
writefln ("%b", n);
writefln ("%b", n ^ 1);
}
-
Output:
-
18446744073709551546
10111010
10111011
-
If you need more than 64 bits, take a look at BitArray here, it
also has xor defined:
http://dlang.org/phobos/std_bitmanip.html#.BitArray
In the future, please explain what problem you are trying to
solve, as the wrong code alone often leaves one guessing.
Ivan Kazmenko.
Re: BigInt and xor
On Tuesday, 24 March 2015 at 15:45:36 UTC, Dennis Ritchie wrote:
Tell me, please, how can I replace this code?
import std.conv : to;
import std.bigint : BigInt;
import std.string : format;
import std.stdio : writeln;
void main() {
BigInt[10] bitArr;
ulong n = 18_446_724_073_709_551_614U;
bitArr[0] = format("%b", n).to!BigInt;
writeln(bitArr[0]);
writeln(bitArr[0] ^ 1); // not work
}
Output:
11101101110001100011000110101010
11101101110001100011000110101011
Hi,
Well it works, the las bit is flip isn't it ? What are you trying
to achieve ?
Re: BigInt and xor
On Tuesday, 24 March 2015 at 15:45:36 UTC, Dennis Ritchie wrote:
Tell me, please, how can I replace this code?
import std.conv : to;
import std.bigint : BigInt;
import std.string : format;
import std.stdio : writeln;
void main() {
BigInt[10] bitArr;
ulong n = 18_446_724_073_709_551_614U;
bitArr[0] = format("%b", n).to!BigInt;
writeln(bitArr[0]);
writeln(bitArr[0] ^ 1); // not work
}
Output:
11101101110001100011000110101010
11101101110001100011000110101011
Looks right to me. What output would you expect?
Also, if you need a bit array you can simply use std.container's
Array!bool. It's specialized for bool and uses only one bit per
element.
BigInt and xor
Tell me, please, how can I replace this code?
import std.conv : to;
import std.bigint : BigInt;
import std.string : format;
import std.stdio : writeln;
void main() {
BigInt[10] bitArr;
ulong n = 18_446_724_073_709_551_614U;
bitArr[0] = format("%b", n).to!BigInt;
writeln(bitArr[0]);
writeln(bitArr[0] ^ 1); // not work
}
Output:
11101101110001100011000110101010
11101101110001100011000110101011
Re: BigInt and >>>
Great! Thanks a lot. Kind regards André On Friday, 19 December 2014 at 08:47:50 UTC, bearophile wrote: Andre: Do you have any idea how to translate the coding correctly? Try: i += long(buffer[3]) << 24 >>> 0; But I also suggest to add parentheses, to make the code less unreadable for humans. Bye, bearophile
Re: BigInt and >>>
Andre: Do you have any idea how to translate the coding correctly? Try: i += long(buffer[3]) << 24 >>> 0; But I also suggest to add parentheses, to make the code less unreadable for humans. Bye, bearophile
BigInt and >>>
Hi,
I try to translate following javascript coding to D:
i = buffer[2] << 16;
i |= buffer[1] << 8;
i |= buffer[0];
i += buffer[3] << 24 >>> 0;
Buffer is:
[255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 111]
Expected result for i is: 4294967295
But in D the last statement returns -1, the previous 3 statements
returns the same values like in JavaScript.
I tried "long" and also like in the example "BigInt", both do not
work correctly. In the documentation it is also mentioned that
is not supported for "BigInt"?
void main()
{
import std.stdio;
import std.bigInt;
auto buffer = [255, 255, 255, 255, 255, 255, 255, 255, 255, 255,
255, 255, 255, 255, 255, 111];
BigInt i;
i = buffer[2] << 16;
i |= buffer[1] << 8;
i |= buffer[0];
i += buffer[3] << 24 >>> 0;
writeln("i: ", i);
}
Do you have any idea how to translate the coding correctly?
Kind regards
André
Re: Cantor tuple function, BigInt, and integer overflow
On Thu, Dec 20, 2012 at 07:46:39PM +0100, Joseph Rushton Wakeling wrote: > Hello all, > > I've been playing around trying to implement the Cantor tuple function > (see attached code), which is essentially a way to map a sequence x1, > x2, ..., xN of non-negative integers to a single unique number. See: > https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function > > The inspiration came from a need to check pairs of numbers for > uniqueness. This is an interesting problem. It is related to the computation of the Cartesian product of infinite ranges: your unique number is simply the index of the given pair in the range over the N-ary Cartesian product of the natural numbers. Of course, it's very inefficient to compute the Cartesian product just to find the index of a particular sequence, so a direct mapping is desirable. The simplest method, mathematically speaking, is to make use of the Prime Factorization theorem, that every non-negative integer is the product of a unique set of primes powers. So to find the index of a sequence, simply assign consecutive primes to them, say 2, 3, 5, 7, 11, 13, ... up to the N'th prime. Then the index is given by: I = 2^x1 * 3^x2 * 5^x3 * ... * pN^xN This index is mathematically guaranteed to be unique for every sequence. However, the problem with this is that it tends to produce very, VERY large numbers, and is rather expensive to compute to boot. Given that we're working on computers where the bit width of x1...xN is fixed (currently 32-bit or 64-bit), we can do better. If we concatenate the elements of the sequence to form a 32*N (or 64*N) bit BigInt, that also gives us a unique index for the sequence. Assuming that the numbers in your sequence cover a good part of the range of a 32-bit (or 64-bit) integer, this encoding produces much smaller numbers than the prime product method. But then, concatenation just means that you might as well just store the sequence as-is (since that's what concatenation amounts to!), and make comparisons based on that. However, you probably want to have a faster means of comparison. And so this is where hashtables come in: if you only have a relatively small number of sequences (compared with the potentially wide range of values of elements in the sequence and wide variance of sequence length), then computing huge unique indices for them is overkill. A more efficient method is to compute a hash for the sequence that has a low collision rate, and for colliding entries just keep a simple list of some sort containing the actual sequences, so that you can fallback to bitwise comparison. IOW, bool[Sequence] may be all you need to solve your problem, depending on what you're trying to do. T -- I see that you JS got Bach.
Cantor tuple function, BigInt, and integer overflow
Hello all,
I've been playing around trying to implement the Cantor tuple function (see
attached code), which is essentially a way to map a sequence x1, x2, ..., xN of
non-negative integers to a single unique number. See:
https://en.wikipedia.org/wiki/Pairing_function#Cantor_pairing_function
The inspiration came from a need to check pairs of numbers for uniqueness.
The current implementation is a bit stupid and naive (it falls into the same
trap as Andrei identifies in TDPL for the naive recursive Fibonacci function),
but that's a deliberate short-term choice just to get something working-ish.
The challenge here is that as the sequence length increases, we very quickly get
to the point where the number calculated will overflow the bounds of any inbuilt
integer type. Indeed, even where you're just dealing with a pair of numbers,
you risk overflow if the values are close to the maximum of their given type.
For this reason I've made use of BigInt internally and as a return value.
However, it occurs to me that it would be nice to avoid BigInt unless it's
necessary, both for speed/memory reasons and for convenience. I'm wondering if
anyone has any advice on how to do this safely, i.e. to definitively check that
whether overflow is going to happen and if it is, to make use of a larger-scale
type.
I'd also like to be able to implement the cantorPair function so that it can
take any integer input _including_ BigInt; however, implementing a templated
version runs into the difficulty of clashing with the BigInt version. One
approach I tried involved a private function taking only BigInt input, with a
templated version that takes arbitrary input types and converts them. This ran
into trouble since I could not find a ready way to check if an input was itself
a BigInt. So again, any advice here is welcome. :-)
Incidentally, a few notes on BigInt:
-- it would be nice if there was a toULong as well as a toLong function
-- the following fails:
BigInt x = BigInt(y);
... if y is itself a BigInt. Worth adding to BigInt's constructor to
correct this?
Advice, thoughts, etc., welcome. This seemed like something that could be
useful for Phobos if cleaned up and well implemented ?
import std.bigint, std.conv, std.exception, std.math, std.range, std.stdio, std.traits;
BigInt cantorPair(BigInt x, BigInt y)
{
enforce(x >= 0);
enforce(y >= 0);
return ((x + y)*(x + y + 1))/2 + y;
}
BigInt cantorTuple(R)(R r)
if(isInputRange!R && hasLength!R)
{
enforce(r.length > 0);
if(r.length == 1)
{
enforce(r[$-1] >= 0);
return BigInt(r[$-1]);
}
else
return cantorPair(cantorTuple(r[0 .. $-1]), BigInt(r[$-1]));
}
void main()
{
foreach(n; iota(1, 10))
{
long[] x;
x.length = n;
foreach(i, ref val; x)
val = i;
BigInt c = cantorTuple(x);
writeln(n, "\t", c);
}
writeln();
writeln(cantorTuple([ulong.max, ulong.max]));
writeln(cantorPair(BigInt(ulong.max), BigInt(ulong.max)));
}
