Computing desk
< July 19	<< Jun \| July \| Aug >>	Current desk >

Welcome to the Wikipedia Computing Reference Desk Archives
The page you are currently viewing is a transcluded archive page. While you can leave answers for any questions shown below, please ask new questions on one of the current reference desk pages.

July 20[edit]

Is it possible to make gitk ignore lines changed only by indentation?[edit]

I'm using gitk to view changes to a really long C# source file on Windows 10. Some of the changes have resulted from moving long blocks of code inside an if statement. As a result, gitk shows every line in the blocks as changed, even though the actual changes for these lines is just increased indentation. This makes viewing the results difficult. Is it possible to make gitk ignore lines changed only by indentation? JIP | Talk 15:51, 20 July 2021 (UTC)[reply]

Not very elegant, but you could try comparing outdented versions of the files involved, where "outdenting" means removing leading whitespace from each line. --Lambiam 21:32, 20 July 2021 (UTC)[reply]

The way I am using gitk is that I just give it the full path to the file in question and it pulls the diffs out from my local git repository's history. If I want to compare custom versions of the file, do I have to actually commit them to the repository, or is there a way to give custom input files to gitk? JIP | Talk 00:17, 21 July 2021 (UTC)[reply]

I don't know much about gitk, but I assume it uses git diff internally. Is there a way to specify extra flags to pass to git? The -b or -w flag passed to git diff will do what you want. CodeTalker (talk) 17:44, 21 July 2021 (UTC)[reply]

Which simple challenge you can ask to someone over the phone using common math in order to ask him to prove he as a specific computing power?[edit]

Such type of benchmarking without using a full program is something which usually requires generating large numbers from small numbers. I was thinking about a challenge that takes less than 2 minutes to complete using GMP and ask to provide the first or last 5 digits of the result, but I was unable to find something which can t be heavily simplified to the point a full computer isn t required to compute the result. Or I found formulas that have ambiguous writing when dictated over the phone.

I prefer to prove ram amount over speed if possible. 2A01:E0A:401:A7C0:5CA2:C19F:2FCA:369E (talk) 18:53, 20 July 2021 (UTC)[reply]

You could ask them for the n-th decade in the decimal expansion of π, where n is a humongous number bounded from above by the requirement that – given the amount of compute power and fast random-access memory whose availability needs to be proved – this takes less than 2 minutes when using the fastest known method (currently the Chudnovsky algorithm). --Lambiam 20:27, 20 July 2021 (UTC)[reply]

not working. Trillion digits of π are available online precomputed. It doesn t require a full computer. I was rather thinking about something using powers and factorials. 2A01:E0A:401:A7C0:5CA2:C19F:2FCA:369E (talk) 22:57, 20 July 2021 (UTC)[reply]

Then ask for a bunch of undecimal digits (base 11). --Lambiam 08:41, 21 July 2021 (UTC)[reply]

there s a lack of software in that case whereas base 10 or hex is availaible everywhere. 2A01:E0A:401:A7C0:E0F9:E8E4:9FE5:583A (talk) 12:00, 21 July 2021 (UTC)[reply]

What kind of nonsense is this? Base 19 is clearly superior. ^[FBDB] ᛗᛁᛟᛚᚾᛁᚱPants Tell me all about it. 12:32, 21 July 2021 (UTC)[reply]

But I had an uncontrollable urge to use the word "undecimal", which means what it should mean: not decimal. IMO "undevicesimal" is weird; it should mean: "related to an undevice" – whatever that may be. --Lambiam 21:56, 21 July 2021 (UTC)[reply]

I believe Hashcash will work for you. manya (talk) 08:19, 21 July 2021 (UTC)[reply]

not cross plateform. I need a math formula which can be spelled over a phone call. One should be able to use his high end Casio if the requirement is low. 2A01:E0A:401:A7C0:E0F9:E8E4:9FE5:583A (talk) 12:00, 21 July 2021 (UTC)[reply]

You're asking for a proof of work protocol, and you could do something similar to hashcash. If the person can install GMP on their Casio they can install something like scrypt. 2601:648:8202:350:0:0:0:2B99 (talk) 21:15, 21 July 2021 (UTC)[reply]

It has to be possible to use gmp to solve it, but it s not required. That s why, I thought about factorials since you get large numbers from small numbers, but I didn t found a case which doesn t simplify to much.

Really, this is a math problem as the aim is to find a small math formula where you can pick up 5 consecutive digits from the result without making the case simplifiable. 2A01:E0A:401:A7C0:4897:D6B6:A520:51A1 (talk) 22:41, 21 July 2021 (UTC)[reply]

Is this an instance of an XY problem? --Lambiam 22:00, 21 July 2021 (UTC)[reply]

not directly. 2A01:E0A:401:A7C0:4897:D6B6:A520:51A1 (talk) 22:46, 21 July 2021 (UTC)[reply]

I take that as a "yes". It is certainly within the computing power of my little niece to compute the discrete logarithm

\log _{3}4

in the group

\mathbb {Z} _{7}

, but nevertheless she would be stumped by the challenge, as she has not yet learned the concepts involved. So we must assume that the challenge is such that the challenged respondent is prepared to solve it and does not need to study the concepts involved, find and install software and implement algorithms in the precious "less than 2 minutes" allotted. If the size of the challenge space is

C

(for a challenge expressible in

n

bits,

C\leq 2^{n}

), the respondent could then in principle precompute and store the responses for each of the

C

possible challenges. As long as the storage device allows retrieval within two minutes, they can answer the challenge, even if they have little raw compute power. To make this impossible requires

C

to exceed the capacity of readily available storage devices, which means, to be on the safe side for now (but not for the foreseeable future)

C

should be at least a trillion. For

C=10^{12},

challenges can be stated in 12 decimal digits. The discrete logarithm problem over a carefully chosen group (for suitable candidates, see Discrete logarithm § Cryptography) should do. See also the caveat offered by the Logjam security vulnerability. --Lambiam 09:27, 22 July 2021 (UTC)[reply]

On the other side, the person who need to prove is computational power don’t knows the challenge type which means precomputing is limited.

The problem then is an extraction of the result need to not simplify : dicatating a too long number over the phone is error prone both for the input and the result. Or may you give a typicall example which can be dicatated over the phone please ? 2A01:E0A:401:A7C0:DC8C:3097:9425:9D8 (talk) 21:31, 23 July 2021 (UTC)[reply]

For speed, RC4 can be described easily in a single paragraph. Give a description and an initial seed state then ask for the nth resulting byte(s) from the stream. For RAM, it's trickier, but maybe you could do something with Langton's Ant or Conway's Game of Life? 96.246.93.192 (talk) 16:08, 22 July 2021 (UTC)[reply]

Thinking about it, asking for a portion of the end state of a Langton's Ant run is probably the best option. Its RAM usage grows fairly predictably but the actual end state is difficult to predict, especially if multicolor rules are used, and it's easy enough to describe and implement. 96.246.93.192 (talk) 16:46, 22 July 2021 (UTC)[reply]

You forgot it’s the phone, there’s no file exchange for the hash.

The people who will call me tend to have problems with programming. That’s why I’m looking for a math formula where the simplest case requires maximum computational complexity. 2A01:E0A:401:A7C0:DC8C:3097:9425:9D8 (talk) 21:22, 23 July 2021 (UTC)[reply]

Give them Langton's Ant with some XY coordinates already filled in over the phone, then ask them for the color of the pixels at some other XY coordinates after they're done? Simple big number computation no matter what the number is you'll run into the problem that Wolfram Alpha will just give the answer. 96.246.93.192 (talk) 01:31, 24 July 2021 (UTC)[reply]

What do you mean by “already filled in over the phone” ? It’s the phone. Nothing is sent prior.

Are you sure that by asking a single pixel instead of the whole graph, that the algorithms can’t be simplified ?

Even then, what do you mean by color ? I’m seeing it’s black and white. Please give an example on Wolfram Alpha. 2A01:E0A:401:A7C0:2961:A0C3:39A9:BF88 (talk) 08:26, 24 July 2021 (UTC)[reply]

Describe Langton's Ant, then say "On a 1024x1024 grid that wraps around at the edges, color XY XY XY XY already black, then run Langdon's Ant starting from 0,0 for 100,000 rounds" then when they're done ask them for the color of the grid at a series of given XY coordinates. Solving that problem will require a minimum of 128 KiB of RAM (plus a few hundred bytes likely of overhead). For additional security you could use a multicolor variant of the Ant, to test for more RAM you'd increase the size of the grid and add more steps.

As an example of why Wolfram Alpha existing invalidates simply asking for a big number calculation, see here. 96.246.93.192 (talk) 18:52, 24 July 2021 (UTC)[reply]

Given a (sufficiently) large number n, one can ask for the first five remaining digits of the decimal representation of nⁿ after cutting off the initial 20000 digits and then any ~~trailing~~ leading zero digits. For example, if n = 12345, these five digits in the middle of 12345¹²³⁴⁵ are the underlined digits of ...471037119416662... . So 12345 is "transformed" into 71194. Without the ~~trailing~~ leading zeroes rule, n = 23324 would give rise to 67 (...388190006753802...), but it should instead be transformed into 67538. One can iterate this transformation: 21437 ↦ 21180 ↦ 27447 ↦ 18096 ↦ 39025 ↦ ··· . The challenge could be to produce the 1000th iterate, say, of a randomly picked five-digit number. Whether 1000 is sufficient as a challenge depends on what amount of power needs to be proved. The nature of the challenge should be kept secret from the challenged party; otherwise they can cheat by performing precomputations. That holds, I think, for any approach where the challenge and response can be stated briefly over a telephone line. --Lambiam 16:08, 24 July 2021 (UTC)[reply]

If its’s not for the last digits https://brilliant.org/wiki/finding-the-last-digit-of-a-power/, then there’s approximation functions in order to compute the nth first digits.

Finding a case which does not simplify is not trivial. 2A01:E0A:401:A7C0:2961:A0C3:39A9:BF88 (talk) 16:48, 24 July 2021 (UTC)[reply]

First and last digits are both easily computed, but digits in the middle are not. --Lambiam 23:25, 24 July 2021 (UTC)[reply]

Still easier than computing the number in full.

So what the challenge would looks like in plain speech ? Please write an exampe. 2A01:E0A:401:A7C0:F471:C421:5924:2AFF (talk) 09:58, 25 July 2021 (UTC)[reply]

I don't think it is easier than computing the number in full. --Lambiam 22:48, 25 July 2021 (UTC)[reply]

I would still need an example to understand please. 2A01:E0A:401:A7C0:F471:C421:5924:2AFF (talk) 23:06, 25 July 2021 (UTC)[reply]

A five-digit number can be transformed into a new five-digit number by raising the given number to its own power, and then discarding the first two-hundred thousand digits of the result and next any leading zero digits. The new number is formed by the first five remaining digits. Iterate this transformation six hundred sixty-six times, beginning with the number six-six-six-six-six, and tell me the final result. --Lambiam 22:06, 26 July 2021 (UTC)[reply]

Instead of integers, use some transcendental or irrational number like pi or sqrt(2) and use multiple level of exponents. Why π^π^π^π could be an integer (for all we know!) StrayBolt (talk) 21:19, 25 July 2021 (UTC)[reply]

But how do you generate such large number for a srqt without getting simplification ? 2A01:E0A:401:A7C0:F471:C421:5924:2AFF (talk) 23:06, 25 July 2021 (UTC)[reply]

Are these people accomplished mathematicians? Most people would be stumped, regardless of the tools they have available, to produce even the first five digits of

\pi ^{\pi ^{\pi ^{\pi }}}.

(which I think are 90802). A mathematician might be able to pull that off, but probably not within two minutes, although the actual computation requires less than a second of CPU time. I do not think we will be able to suggest a challenge that you'll be satisfied with unless we know more about the mathematical prowess of the other party (especially in the field of numerical mathematics), the software tools that are available to them, and the required speed of their computing platform expressed in some objective measure (even if possibly meaningless, such as MIPS). --Lambiam 11:34, 26 July 2021 (UTC)[reply]

Not directly, I would say the math level expected from someone with a Master degree in programming. 2A01:E0A:401:A7C0:C57C:7E17:68F3:AAA3 (talk) 19:24, 26 July 2021 (UTC)[reply]

I've met CS graduates with only a dim command of high-school algebra, so my expectations are then not that high. But this provides only one aspect of the info needed, and in fact the least essential one. Do you yourself have the means to check the correctness of the response? Is it really necessary that the communication is by voice? That restriction makes what you want almost or perhaps actually impossible, and I have heard that nowadays a global system of pipes for transferring digitized texts almost instantly is conveniently accessible. --Lambiam 21:54, 26 July 2021 (UTC)[reply]

Yes, I can check the correctness of the response, or rather it has to be done automatically and precomputed as the challenge is managed by Voicemail. About the level, maybe it’s because of https://en.wikipedia.org/wiki/Diplôme_d%27Ingénieur which carry a deep instance on learning math in my country. 2A01:E0A:401:A7C0:C57C:7E17:68F3:AAA3 (talk) 10:11, 27 July 2021 (UTC)[reply]