mersenneforum.org  

Go Back   mersenneforum.org > Math Stuff > Other Mathematical Topics

Reply
 
Thread Tools
Old 2019-03-29, 19:00   #1
petrw1
1976 Toyota Corona years forever!
 
petrw1's Avatar
 
"Wayne"
Nov 2006
Saskatchewan, Canada

2×32×11×23 Posts
Default New way to multiply

I don't feel like subscribing so if anyone already is on NewScientist feel free to comment:

https://www.newscientist.com/article...bers-together/
petrw1 is offline   Reply With Quote
Old 2019-03-29, 19:32   #2
Uncwilly
6809 > 6502
 
Uncwilly's Avatar
 
"""""""""""""""""""
Aug 2003
101×103 Posts

22·3·11·71 Posts
Default

Quote:
Originally Posted by petrw1 View Post
I don't feel like subscribing so if anyone already is on NewScientist feel free to comment:

https://www.newscientist.com/article...bers-together/
Link to the original paper: https://hal.archives-ouvertes.fr/hal-02070778/document
Uncwilly is online now   Reply With Quote
Old 2019-03-29, 20:29   #3
GP2
 
GP2's Avatar
 
Sep 2003

32×7×41 Posts
Default

Of little practical use, apparently, except for impossibly large numbers.
GP2 is offline   Reply With Quote
Old 2019-03-29, 22:35   #4
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5×172 Posts
Default

Quote:
Originally Posted by Uncwilly View Post
That is still much slower than Knuth's linear time multiplication algorithm.
R. Gerbicz is offline   Reply With Quote
Old 2019-03-29, 22:58   #5
Mysticial
 
Mysticial's Avatar
 
Sep 2016

331 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
That is still much slower than Knuth's linear time multiplication algorithm.
I'd be more interested in complexities in terms of memory for all these algorithms.

IOW, given a memory latency/bandwidth curve, (where further away means higher latency + less bandwidth), what's the run-time complexity? Right now, it's not entirely representative of real hardware since that curve is a step function for each of the levels of cache/memory/disk, etc...

But let's think (very) big here since the new paper is about impractically big sizes anyway.

Given these assumptions:
  • You cannot transmit information faster than the speed of light.
  • There is a limit to how dense you can store data. (Planck's constant)
  • There are only 3 known spatial dimensions that we can utilize.
The latency curve will be (required memory)^(1/3) or about O(N^(1/3)) if you pack your memory into a 3D structure such as a sphere.

At larger scales, this won't hold. If you assume that each bit of information requires a minimum (non-zero) amount of mass, then you cannot sustain a 3D structure of fixed density. Because at sufficiently large sizes, that structure will be smaller than its Schwarzschild radius.

The densest infinitely sized structure you can have without it collapsing into a black hole I believe is a pole of infinite length. This means that the average latency to get data between any two points of this "large stick of memory" is going to be O(N). This is much worse than O(N^(1/3)).

But this is just for latency since we're bounded by the speed of light. Bandwidth seems harder to theorize. Is it possible to transmit an infinite amount of information through a finite amount of space? (a naive extrapolation of simple EM wave addition says it is)


p.s. Not being a theoretical physicist, I'm not sure on the assertion that there is a minimum space and mass to storing a bit of information. It may be possible to do some sort of infinite superposition of EM waves or quantum state.

Last fiddled with by Mysticial on 2019-03-29 at 23:05
Mysticial is offline   Reply With Quote
Old 2019-03-29, 23:16   #6
R. Gerbicz
 
R. Gerbicz's Avatar
 
"Robert Gerbicz"
Oct 2005
Hungary

5·172 Posts
Default

Quote:
Originally Posted by Mysticial View Post
Given these assumptions:
  • You cannot transmit information faster than the speed of light.
What about quantum entanglement?
R. Gerbicz is offline   Reply With Quote
Old 2019-03-29, 23:26   #7
Mysticial
 
Mysticial's Avatar
 
Sep 2016

331 Posts
Default

Quote:
Originally Posted by R. Gerbicz View Post
What about quantum entanglement?
I'm obviously not an expert in this area, but I don't think quantum entanglement can allow FTL transmission of information.

From what I understand, any method of transmitting information faster than the speed of light can then be used to travel backwards in time and violate causality.

If we allow time travel, then things get complicated enough that I'm not sure I want to think about it.


-----


Come to think of it. I'm not sure the concept of "time-complexity" in the presence of time travel is that interesting. Because you can take as long as you want to compute the result and then send it back to yourself in the past. Thus taking zero (or negative) time.

If you can't "take as long as you want" because you'll run up against the heat death of the universe or something, then you can split it up. Do the computation in chunks and send it back to yourself before the "end" to continue it. Rinse and repeat...

Last fiddled with by Mysticial on 2019-03-29 at 23:43
Mysticial is offline   Reply With Quote
Old 2019-03-30, 00:08   #8
a1call
 
a1call's Avatar
 
"Rashid Naimi"
Oct 2015
Remote to Here/There

26·31 Posts
Default

Quantum entanglement can not be used to transmit information FTL. It invoves apparent synchronicity in random aspects of entangled particles.
one thing that involves instant travel in the Micro world is Quantum -Tunneling.

Here is what The-Infallible-Source has to say about it :

Quote:
Some physicists have claimed that it is possible for spin-zero particles to travel faster than the speed of light when tunnelling.[3] This apparently violates the principle of causality, since there will be a frame of reference in which it arrives before it has left. In 1998, Francis E. Low reviewed briefly the phenomenon of zero-time tunnelling.[31] More recently experimental tunnelling time data of phonons, photons, and electrons have been published by Günter Nimtz.[32]

Other physicists, such as Herbert Winful,[33] have disputed these claims. Winful argues that the wavepacket of a tunnelling particle propagates locally, so a particle can't tunnel through the barrier non-locally. Winful also argues that the experiments that are purported to show non-local propagation have been misinterpreted. In particular, the group velocity of a wavepacket does not measure its speed, but is related to the amount of time the wavepacket is stored in the barrier.
https://en.wikipedia.org/wiki/Quantu...ter_than_light


Link to Video

Last fiddled with by a1call on 2019-03-30 at 00:16
a1call is offline   Reply With Quote
Reply

Thread Tools


Similar Threads
Thread Thread Starter Forum Replies Last Post
Multiply Pandigital 2 davar55 Puzzles 3 2013-01-07 20:23
Multiply Pandigital davar55 Puzzles 18 2010-12-22 22:07
Multiply mgb Lounge 0 2008-07-28 12:54
Multiply Perfect Numbers grandpascorpion Math 5 2006-11-24 19:47
Critical bug in Gnu MP FFT-multiply code ET_ Lounge 3 2004-03-11 16:24

All times are UTC. The time now is 14:15.

Fri Mar 5 14:15:25 UTC 2021 up 92 days, 10:26, 0 users, load averages: 2.04, 2.50, 2.64

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.