mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Abstract Algebra & Algebraic Number Theory

Reply
 
Thread Tools
Old 2017-06-29, 01:48   #12
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by manasi View Post
1. I need to find out a program that only deals in machine level 0s and 1s. What I mean is unlike C++, Java, etc...decimals are not converted to binary but it is a program where every number dealing is binary.
In almost every modern language, certainly including PARI/GP, C++, and Java, all numbers are in binary unless you go through a lot of extra effort to avoid that (via BCD or other formats). You enter numbers in decimal, but they are stored and processed exclusively in binary and only re-converted into decimal when you output them.

Quote:
Originally Posted by manasi View Post
There should be no fixed integer range so large blocks can be dealt with in a good way.
This only slightly less common. Some languages like PARI/GP and Python have bignums built-in so you can't reasonably overflow, and many others like C and Java have libraries that can support them as needed.
CRGreathouse is offline   Reply With Quote
Old 2017-06-29, 10:11   #13
manasi
 
Jun 2017

13 Posts
Default

Quote:
Originally Posted by paulunderwood View Post
If you have linux you could use the bc language:

Code:
bc 1.06.95
Copyright 1991-1994, 1997, 1998, 2000, 2004, 2006 Free Software Foundation, Inc.
This is free software with ABSOLUTELY NO WARRANTY.
For details type `warranty'. 
ibase=2
obase=2
101010*101001
11010111010
I think you can get it for Windows and iPhone
Thanks
manasi is offline   Reply With Quote
Old 2017-06-29, 10:13   #14
manasi
 
Jun 2017

13 Posts
Default

Quote:
Originally Posted by Dubslow View Post
Do you mean something like GMP?

Yes, every language still fundamentally works in binary, but typically in fixed-width binary. GMP is a library for C (and therefore all its derivatives) that allows for arbitrary-size integers. It's very common in big number prime testing and factorization code.

https://en.wikipedia.org/wiki/List_o...metic_software

A lot of the languages and software packages in the above list use GMP under the hood.
Thanks. I learnt about GMP. I was talking about ASCII specifications and space a signed or unsigned int occupies. I will explain in next post.

Last fiddled with by manasi on 2017-06-29 at 10:14
manasi is offline   Reply With Quote
Old 2017-06-29, 10:19   #15
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×2,417 Posts
Default

I am probably wrong on this, but... Isn't the use of fixed length variables a matter of the machine word length, i.e. hardware stuff, not software stuff?

In other words, the use of decimal, binary, hexadecimal or whatever else is bound to the physical representation of the bits inside the computer registers. This means that a "binary, unbound bit-length language" is something as theoretical as a Turing Machine...
ET_ is offline   Reply With Quote
Old 2017-06-29, 10:23   #16
manasi
 
Jun 2017

11012 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
In almost every modern language, certainly including PARI/GP, C++, and Java, all numbers are in binary unless you go through a lot of extra effort to avoid that (via BCD or other formats). You enter numbers in decimal, but they are stored and processed exclusively in binary and only re-converted into decimal when you output them.
Well, the only problem is there is a certain integer range that is acceptable as space for an integer(signed or unsigned int). There is a problem if you have to check a number like 2^10000019 -1 is prime or not. Most programs can not handle operations with large numbers.

Now, suppose I do not want to use Lucas Lehmer test but instead want to create endomorphisms that directly alter blocks of the binary sequence 2^10000019 -1 yielding a result with less operations. For instance, you could rule out division from {multiplication,division,subtraction} but only use {subtraction,multiplication}. There would be very large binary sequences. This is what I want to do to get results a different way.


Quote:
Originally Posted by CRGreathouse View Post
This only slightly less common. Some languages like PARI/GP and Python have bignums built-in so you can't reasonably overflow, and many others like C and Java have libraries that can support them as needed.
Oh!

Last fiddled with by CRGreathouse on 2017-06-29 at 14:46 Reason: fix quote tag
manasi is offline   Reply With Quote
Old 2017-06-29, 10:51   #17
ET_
Banned
 
ET_'s Avatar
 
"Luigi"
Aug 2002
Team Italia

2×2,417 Posts
Default

Quote:
Originally Posted by manasi View Post
Now, suppose I do not want to use Lucas Lehmer test but instead want to create endomorphisms that directly alter blocks of the binary sequence 2^10000019 -1 yielding a result with less operations. For instance, you could rule out division from {multiplication,division,subtraction} but only use {subtraction,multiplication}. There would be very large binary sequences. This is what I want to do to get results a different way.




Oh!
Montgomery multiplication and binary exponentiation?
ET_ is offline   Reply With Quote
Old 2017-06-29, 14:45   #18
CRGreathouse
 
CRGreathouse's Avatar
 
Aug 2006

3·1,993 Posts
Default

Quote:
Originally Posted by manasi View Post
Now, suppose I do not want to use Lucas Lehmer test but instead want to create endomorphisms that directly alter blocks of the binary sequence 2^10000019 -1 yielding a result with less operations.
I don't know why you think it is possible to go faster than LL by working "directly"with binary. All existing programs work directly with binary.

Last fiddled with by CRGreathouse on 2017-06-29 at 14:46
CRGreathouse is offline   Reply With Quote
Old 2017-06-29, 16:32   #19
Batalov
 
Batalov's Avatar
 
"Serge"
Mar 2008
Phi(4,2^7658614+1)/2

25×7×43 Posts
Default

Quote:
Originally Posted by manasi View Post
Most programs can not handle operations with large numbers.
Depends on what you call 'most'. Excel? calc.exe?

Quote:
Originally Posted by manasi View Post
... This is what I want to do to get results a different way.

... Oh!
In order to get results a different way you first need to read and learn what is already done.

Two Russian anecdotes come to mind:
1. "Can you play violin?" -- "I never tried but I think I can!". This was popular [I]long[/I] before the Kruger & Dunning 1999 paper.
2. "Can you play (using a)* violin?" -- "I can! ...But it is very inconvenient - the cards** slip and fall over. Cello is much better."
______________
*In Russian, "to play violin" is a phrase with a preposition.
**And of course "play" in most minds means "play cards"
Batalov is offline   Reply With Quote
Old 2017-06-29, 18:34   #20
manasi
 
Jun 2017

13 Posts
Default

Quote:
Originally Posted by ET_ View Post
Montgomery multiplication and binary exponentiation?
I thought to use endomorphisms and work similar to modular arithmetic -

Start to compare size of two binary numbers minus zeroes at the end. Then just play with the blocks using endomorphisms. Different algorithm other than the two you mentioned. But then, as you say, perhaps machine specifies integer width.(hardware) So, I can not proceed on this line.
manasi is offline   Reply With Quote
Old 2017-06-29, 18:36   #21
manasi
 
Jun 2017

13 Posts
Default

Quote:
Originally Posted by CRGreathouse View Post
I don't know why you think it is possible to go faster than LL
No idea if I can go faster. Didn't exactly write and compare the two algorithms. Just wanted to try different.
manasi is offline   Reply With Quote
Old 2017-06-29, 18:38   #22
manasi
 
Jun 2017

13 Posts
Default

Quote:
Originally Posted by Batalov View Post


In order to get results a different way you first need to read and learn what is already done.
Thanks.
Very true.(i) I would like to know more about endomorphisms acting on binary sequences. (ii) Are they more/less helpful in factoring? I googled but did not get suitable results.

Last fiddled with by manasi on 2017-06-29 at 18:39
manasi is offline   Reply With Quote
Reply

Thread Tools


All times are UTC. The time now is 22:39.


Wed Dec 8 22:39:00 UTC 2021 up 138 days, 17:07, 0 users, load averages: 2.72, 1.80, 1.57

Powered by vBulletin® Version 3.8.11
Copyright ©2000 - 2021, Jelsoft Enterprises Ltd.

This forum has received and complied with 0 (zero) government requests for information.

Permission is granted to copy, distribute and/or modify this document under the terms of the GNU Free Documentation License, Version 1.2 or any later version published by the Free Software Foundation.
A copy of the license is included in the FAQ.