Fastest way to compute 9^(9^9) exactly all digits?

Is there a way to exactly compute all of the ca. 370 million decimal digits of 9^(9^9) very fast? I used an out of the box bignumber algorithms library(*) which took 16 minutes.

(*) I used Java BigInteger the pow() method:

?- time((_ is 9^(9^9))).
% Up 974,318 ms, GC 9,302 ms, Thread Cpu 962,688 ms (Current 06/01/18
19:54:01)
Yes

?- statistics.
Max Memory           7,635,730,432 Bytes
Used Memory           765,913,440 Bytes
Free Memory          2,891,739,304 Bytes
Uptime                 2,466,670 Millis
GC Time                    9,315 Millis
Thread Cpu Time          963,812 Millis
Current Time          06/01/18 20:18:37 

The Java BigInteger implementation uses Karatsuba and Toom Cook:
http://hg.openjdk.java.net/jdk8/jdk8/jdk/file/tip/src/share/classes/java/math/BigInteger.java

P.S.: To additionally output the ca. 370 million decimal digits, if it would use 1 ms per digit, would only need 370’000 ms. Thats a third of the time I needed to compute the exact digits in the above, i.e. 974,318 ms without displaying.

Solution:

Try https://raw.githubusercontent.com/tbuktu/bigint/master/src/main/java/java/math/BigInteger.java for an improved BigInteger that switches to Schoenhage-Strassen once integers get past 74,000 digits. My back of the envelope says that that should be an order of magnitude faster after you get to hundreds of millions of digits.

Advertisements

Crash when trying to run WebGoat with a Java Agent

I am currently learning how to boot a web application with a java agent for monitoring.

The Web Application I chose was WebGoat, and running WebGoat with java -jar webgoat-server-8.0.0.M17.jar as stated in WebGoat’s README works perfectly fine.

However, when I try to add my agent, I get the following mess of an error log:

  .   ____          _            __ _ _
 /\\ / ___'_ __ _ _(_)_ __  __ _ \ \ \ \
( ( )\___ | '_ | '_| | '_ \/ _` | \ \ \ \
 \\/  ___)| |_)| | | | | || (_| |  ) ) ) )
  '  |____| .__|_| |_|_| |_\__, | / / / /
 =========|_|==============|___/=/_/_/_/
 :: Spring Boot ::       (v1.5.12.RELEASE)

2018-06-06 22:36:08.528  INFO 3741 --- [           main] org.owasp.webgoat.StartWebGoat           : Starting StartWebGoat v8.0.0.M17 on MacBook-Pro.local with PID 3741 (/Users/andrewfan/Desktop/Lang Agent Dev Proj help info/webgoat-server-8.0.0.M17.jar started by andrewfan in /Users/andrewfan/Desktop/Lang Agent Dev Proj help info)
2018-06-06 22:36:08.531  INFO 3741 --- [           main] org.owasp.webgoat.StartWebGoat           : No active profile set, falling back to default profiles: default
2018-06-06 22:36:08.844  INFO 3741 --- [           main] ationConfigEmbeddedWebApplicationContext : Refreshing org.springframework.boot.context.embedded.AnnotationConfigEmbeddedWebApplicationContext@1376c05c: startup date [Wed Jun 06 22:36:08 EDT 2018]; root of context hierarchy
2018-06-06 22:36:11.354  INFO 3741 --- [           main] trationDelegate$BeanPostProcessorChecker : Bean 'org.springframework.transaction.annotation.ProxyTransactionManagementConfiguration' of type [org.springframework.transaction.annotation.ProxyTransactionManagementConfiguration$$EnhancerBySpringCGLIB$$8e12590a] is not eligible for getting processed by all BeanPostProcessors (for example: not eligible for auto-proxying)
2018-06-06 22:36:11.442  WARN 3741 --- [           main] ationConfigEmbeddedWebApplicationContext : Exception encountered during context initialization - cancelling refresh attempt: org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'mvcConfiguration': Injection of autowired dependencies failed; nested exception is java.lang.IllegalArgumentException: Could not resolve placeholder 'webgoat.user.directory' in value "${webgoat.user.directory}"
2018-06-06 22:36:11.455  INFO 3741 --- [           main] utoConfigurationReportLoggingInitializer : 

Error starting ApplicationContext. To display the auto-configuration report re-run your application with 'debug' enabled.
2018-06-06 22:36:11.464 ERROR 3741 --- [           main] o.s.boot.SpringApplication               : Application startup failed

org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'mvcConfiguration': Injection of autowired dependencies failed; nested exception is java.lang.IllegalArgumentException: Could not resolve placeholder 'webgoat.user.directory' in value "${webgoat.user.directory}"
    at org.springframework.beans.factory.annotation.AutowiredAnnotationBeanPostProcessor.postProcessPropertyValues(AutowiredAnnotationBeanPostProcessor.java:372) ~[spring-beans-4.3.16.RELEASE.jar!/:4.3.16.RELEASE]
    at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.populateBean(AbstractAutowireCapableBeanFactory.java:1268) ~[spring-beans-4.3.16.RELEASE.jar!/:4.3.16.RELEASE]
    at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.doCreateBean(AbstractAutowireCapableBeanFactory.java:553) ~[spring-beans-4.3.16.RELEASE.jar!/:4.3.16.RELEASE]
    at org.springframework.beans.factory.support.AbstractAutowireCapableBeanFactory.createBean(AbstractAutowireCapableBeanFactory.java:483) ~[spring-beans-4.3.16.RELEASE.jar!/:4.3.16.RELEASE]
    at org.springframework.beans.factory.support.AbstractBeanFactory$1.getObject(AbstractBeanFactory.java:312) ~[spring-beans-4.3.16.RELEASE.jar!/:4.3.16.RELEASE]
    at 

I cut the error messages short since the trace is a few pages long, but the main error seems to be org.springframework.beans.factory.BeanCreationException: Error creating bean with name 'mvcConfiguration': Injection of autowired dependencies failed; nested exception is java.lang.IllegalArgumentException: Could not resolve placeholder 'webgoat.user.directory' in value "${webgoat.user.directory}"


I am running my agent as follows:
java -javaagent:/Users/path/to/jar/Spn-LangAgent-0.0.jar -jar webgoat-server-8.0.0.M17.jar --server.port=8080 --server.address=localhost

My agent is as follows:

package com.spnlangagent.langagent;

import java.io.File;
import java.nio.file.Files;
import java.nio.file.StandardCopyOption;
import java.io.IOException;
import java.io.InputStream;
import java.net.URL;
import java.net.URLClassLoader;
import java.lang.reflect.Field;
import java.lang.instrument.Instrumentation;
import java.lang.instrument.UnmodifiableClassException;

import com.google.monitoring.runtime.instrumentation.AllocationRecorder;

public class LangAgent {

    public static void premain(String agentArgs, Instrumentation inst) throws Exception {
        System.out.println("LangAgent: premain now running");
        setupInstrumentation(agentArgs, inst);
        startRuntime(agentArgs);
    }

    private static void setupInstrumentation(String agentArgs, Instrumentation inst) throws Exception {
        System.out.println("setupInstrumentation: now running with agentArgs: " + agentArgs);
    }

    private static void startRuntime(String agentArgs) throws Exception {
        System.out.println("startRuntime: now running with agentArgs: " + agentArgs);
    }
}

The original contents of the agent were commented out except for a few print statements, and yet even with this, WebGoat is crashing on startup.

I tried another agent with WebGoat and it worked fine, so the only thing I can think of is that something is wrong with either my agent, or the way it is being packaged.

I am using Maven, and my MANIFEST.MF is as follows:

Manifest-Version: 1.0
Premain-Class: com.spnlangagent.langagent.LangAgent
Can-Redefine-Classes: true
Can-Retransform-Classes: true

After running mvn package, the MANIFEST packaged in the .jar is as follows:

Manifest-Version: 1.0
Premain-Class: com.spnlangagent.langagent.LangAgent
Built-By: andrewfan
Can-Redefine-Classes: true
Can-Retransform-Classes: true
Created-By: Apache Maven 3.5.3
Build-Jdk: 1.8.0_172

In my pom.xml, I am doing the following to reach the manifest:

         <plugin>
            <groupId>org.apache.maven.plugins</groupId>
            <artifactId>maven-jar-plugin</artifactId>
            <version>3.1.0</version>
            <configuration>
                <archive>
                    <manifestFile>src/main/resources/META-INF/MANIFEST.MF</manifestFile>
                </archive>
            </configuration>
        </plugin>

If someone could point me in the right direction in regards to figuring out why WebGoat is crashing, or if someone could provide more insight into why what I am currently doing is wrong, that would be greatly appreciated.

Thank you.

Note: If the rest of my pom.xml is necessary for debugging, I will gladly provide it; it’s just that the question is already very long as-is.

Solution:

Webgoat (and also in most Spring-based application) relies on properties file (in properties or yaml format usually) to perform placeholder lookup.

The symptom in your failure indicate that Spring failed to lookup properties for placeholder processing.

Given that placeholder lookup works well without presence of your agent JAR, and with information you mentioned in comment, the problem is caused by

  • Your agent JAR provided application.properties (which has name collision with the properties file used by Webgoat for placeholder)
  • Agent JAR will be part of classpath, and probably even appear earlier than the main JAR
  • your empty application.properties “shadowed” the one in Webgoat main JAR. Which means, when Webgoat starts, Spring picked up your empty application.properties for its placeholder processing, hence failed.

Thymeleaf in IntelliJ: cannot resolve variables

Intellij Not Recognizing Model Variables in HTML. How to resolve model variables. I don’t get any idea for this issue.

Here is my Controller

@Controller 
public void someController {
  @RequestMapping("/")
  public String someMethod() {
    model.addAttribute("message", "message");
    return "index";
}

And here is my “index.html”

<p th:text="${message}"> </p>

and of course in my html tag i’m using thymeleaf :

<html xmlns:th="http://www.thymeleaf.org" xmlns="http://www.w3.org/1999/html">

the problem is in myth:text="${message}" i see red squiggly lines saying that “Cannot resolve “message” variable…”

Solution:

I’ve been ignoring that issue for as long as I’ve been using Thymeleaf. Even though it shows the squiggly lines, it should still work when you run the application.

IntelliJ would almost have to compile the code in the background to be able to automatically (and accurately, since you could have multiple methods who uses the same template) resolve the variables.

I’ve never given a tip like this, but after reading your comment that you just find the wiggly line annoying, I decided to suggest it anyways:

Disable the tip.

configure inspections

disable expression variables validation

I feel absolutely barbaric for posting this answer, forgive me SO

About special characters in java

In my application about World of Warcraft mythic dungeons i have to do some queries into the raiderio Public API. I having a big issue when the players name it’s something like this :

https://raider.io/api/v1/characters/profile?region=US&realm=https://raider.io/characters/us/zuljin/Børomìr&name=&fields=mythic_plus_best_runs%3Aall

this name : Børomìr

In the API this query doesn’t work because it manages special characters like this:

https://raider.io/api/v1/characters/profile?region=us&realm=zuljin&name=B%C3%B8rom%C3%ACr&fields=mythic_plus_best_runs%3Aall

becomes this : B%C3%B8rom%C3%ACr

where:

ø becomes %C3%B8

ì becomes %C3%AC

which tool do i need to generate this conversion in java?

Heres is the URL request code:

            String body = "";
            URL url = new URL("https://raider.io/api/v1/characters/profile?region="+region.toString()+"&realm="+realm+"&name="+name+"&fields=mythic_plus_best_runs%3Aall");
            System.out.println(url.toString());
            URLConnection uc = url.openConnection();
            uc.addRequestProperty("User-Agent", "Mozilla/4.0 (compatible; MSIE 6.0; Windows NT 5.0)");
            InputStream in = uc.getInputStream();
            String encoding = uc.getContentEncoding();
            encoding = encoding == null ? "UTF-8"
                    // "windows-1251"
                    // "Cp1251"
                    : encoding;
            body = IOUtils.toString(in, encoding);

Solution:

You would use Java’s URLEncoder As in URLEncoder.encode("Børomìr", "UTF-8");

Finding the least double greater than in Java

Is there a built-in method to find the next greatest double number in Java?

When writing a test, I sometimes want to verify that an operation succeeds for x but fails for values greater than x. One way to do this is to show that the operations fails for x + eps. But eps must be chosen taking into account the value of x to avoid problems like 180 + 1e-15 == 180.

To automatically select eps, I’d like to find the smallest representable number greater than x. I was surprised that I didn’t find a standard library method, so I wrote the following:

public static double nextDouble(double d) {
    if (d < 0) {
        return -prevDouble(Math.abs(d));
    } else {
        return Double.longBitsToDouble(Double.doubleToLongBits(d) + 1);
    }
}

public static double prevDouble(double d) {
    if (d < 0) {
        return -nextDouble(-d);
    } else {
        return Double.longBitsToDouble(Double.doubleToLongBits(d) - 1);
    }
}

Should I use these custom functions, or is there a built-in approach available?

Solution:

There is the Math.nextUp method.

Returns the floating-point value adjacent to d in the direction of positive infinity.

There are overloads to take double and float. There are also corresponding Math.nextDown methods.

Function .contains() not working in Groovy on expected way

I am trying to check if number is member of list by using Groovy programming language.

I have this piece of code:

List<Long> list = [1, 2, 3]
Long number = 3

println(list.contains(number))​

Expected output is true, but the result I get is false.

Does anybody have an explanation?

Solution:

Generic type parameters don’t feature at runtime. Check this:

List<Long> list = [1, 2, 3]
list.each{println it.getClass()}

Which prints:

class java.lang.Integer
class java.lang.Integer
class java.lang.Integer

The true confusion is introduced by the bizarre behavior difference between .equals and == implementations:

Long.valueOf(3).equals(Integer.valueOf(3))
===> false
Long.valueOf(3) == Integer.valueOf(3)
===> true

List.contains seems to be using .equals, which checks the class of the parameter, thus explaining why forcing element types to Long resolves the problem.

So, in the midst of this uncertainty, I think the only sure thing is that Groovy’s == execution performs the most intuitive and predictable comparison. So I’d change the check to:

boolean contains = list.grep{it == 3L} //sets value to true if matches at least 1

It helps when one doesn’t have to be cognizant of data types linked to literals:

def ints = [1, 2, 3]
def longs = [1L, 2L, 3L]

boolean found1 = ints.grep{it == 3L}
boolean found2 = ints.grep{it == 3}
boolean found3 = longs.grep{it == 3L}
boolean found4 = longs.grep{it == 3}

println found1
println found2
println found3
println found4

Which works as anyone would want:

true
true
true
true

Why can I collect a parallel stream to an arbitrarily large array but not a sequential stream?

From answering this question, I ran into a peculiar feature. The following code works as I assumed it would (the first two values within the existing array would be overridden):

Integer[] newArray = Stream.of(7, 8)
                           .parallel()
                           .toArray(i -> new Integer[] {1, 2, 3, 4, 5, 6});

System.out.println(Arrays.toString(newArray));

Output:

[7, 8, 3, 4, 5, 6]

However, attempting this with a sequential stream throws an IllegalStateException:

Integer[] newArray = Stream.of(7, 8)
                           .toArray(i -> new Integer[] {1, 2, 3, 4, 5, 6});

System.out.println(Arrays.toString(newArray));

Output:

Exception in thread "main" java.lang.IllegalStateException: Begin size 2 is not equal to fixed size 6
    at java.base/java.util.stream.Nodes$FixedNodeBuilder.begin(Nodes.java:1222)
    at java.base/java.util.stream.AbstractPipeline.copyInto(AbstractPipeline.java:483)
    at java.base/java.util.stream.AbstractPipeline.wrapAndCopyInto(AbstractPipeline.java:474)
    at java.base/java.util.stream.AbstractPipeline.evaluate(AbstractPipeline.java:550)
    at java.base/java.util.stream.AbstractPipeline.evaluateToArrayNode(AbstractPipeline.java:260)
    at java.base/java.util.stream.ReferencePipeline.toArray(ReferencePipeline.java:517)
    at test/test.Test.main(Test.java:30)

I’m curious as to why the sequential stream does not overwrite elements of the array as the parallel stream does. I searched around a bit and was not able to find documentation regarding this, but I assume it exists somewhere.

Solution:

The generator function is required to produce “a new array of the desired type and the provided length.” If you don’t comply with the spec, behavior is undefined.